Sorting algorithms aren't usually tested alone. They are often paired with another problem type and the goal is to really see if you're able to think about the algorithms in a wider context
Bubble Sort
Selection Sort
Insertion Sort
Merge Sort
Quick Sort
Counting Sort
Bucket Sort
  • Traverse from left to right, swap element with neighbor is neighbor is less than element
  • Repeat till no more swaps are needed
  • Invariant: after every iteration, the largest elements are arranged at the end in ascending order
  • Traverse from left to right, maintaining a “sorted” section in the front of the array
  • Every iteration, we seek the next smallest element in the “unsorted” section and insert to the front
  • Invariant: after iteration
    , the front
    elements are arranged the smallest elements sorted in ascending order
  • Traverse from left to right
  • When encountering a number less than the current element, we move backwards, finding elements before the current element that is greater than the number
  • Repeat till a smaller number found, and then swap the elements into position
  • Invariant: after iteration
    , the front
    elements are arranged in ascending order (no guarantee to be the smallest
O(nlog⁡n)O(n \log n)
  • ​
    T(n)=2T(n/2)+O(n)T(n) = 2T(n/2) + O(n)
  • Break up the array into half and merge at the end
  • Stop breaking it up once only 1 element is left
  • Invariant: the leftmost set of elements will be sorted before the rightmost
# [left, right)
def merge_sort(arr, left, right):
if left == right:
return arr[left]
elif left < right:
mid = left + (right - left) // 2
left_merged = merge_sort(arr, left, mid) # [left, mid)
right_merged = merge_sort(arr, mid, right) # [mid, right)
return merge(left_merged, right_merged)
def merge(a, b):
c = []
i, j = 0, 0
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
j += 1
idx, remaining = (i, a) if i < len(a) else (j, b)
for k in range(idx, len(remaining)):
return c
O(nlog⁡n)O(n\log n)
  • Pick a pivot, partition array around pivot value, and repeat for all halves till 1 element
  • Same recurrence as merge sort
  • If duplicates allowed, use dutch flag algorithm, otherwise, can refer to the partitioning algorithms used in Quick Select​
  • Worst case can be
    if array already sorted
  • ​
    is the number of distinct elements
  • Count frequency of each element
  • Reconstruct the array from the frequency
  • Can appear as ways to re-construct an array that has very little elements but many duplicates
def counting_sort(arr):
offset = min(arr)
freq = [0] * (max(arr) - offset + 1)
for num in arr:
freq[num - offset] += 1
result = []
for i in range(freq):
while freq[i] > 0:
result.append(i + offset)
return result
O(n+n2k+k)O(n + \frac{n^2}{k} + k)
  • For every element in the array, create buckets that correspond to some property (such as value and each bucket is a range)
  • Sort elements of each individual bucket
  • Join all buckets to form result
  • Usually best if
    k≈nk \approx n
    so the overall runtime could be