Drag across the case. Click it, then use ← → to step and Space to play.
Four ways to put things in order, and what each one costs. Insertion sort shifts each element left into place. Merge sort splits in half, sorts each half, then merges. Quick sort partitions around a pivot. Bucket sort counts values that fall in a small range. The array is the same type case as on the Arrays page; extra rows of compartments are the scratch space an algorithm needs. Step through each one and count the comparisons and moves yourself.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift right
j -= 1
arr[j + 1] = key
return arr
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
def merge(a, b):
res, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
return res + a[i:] + b[j:]
def quick_sort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return arr
p = partition(arr, lo, hi)
quick_sort(arr, lo, p - 1)
quick_sort(arr, p + 1, hi)
return arr
def partition(arr, lo, hi): # Lomuto: last element is the pivot
pivot = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= pivot:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
def bucket_sort(arr, max_val):
# 1. Count: one bucket per possible value, 0..max_val
counts = [0] * (max_val + 1)
for x in arr:
counts[x] += 1
# 2. Overwrite: write each value back as many times as it was counted
i = 0
for val in range(len(counts)):
for _ in range(counts[val]):
arr[i] = val
i += 1
return arr
def merge(intervals): # LeetCode 56
intervals.sort(key=lambda p: p[0]) # sort by start
res = [intervals[0]]
for start, end in intervals[1:]:
if start <= res[-1][1]: # overlaps the last one
res[-1][1] = max(res[-1][1], end)
else:
res.append([start, end])
return res
Values are only 0, 1 and 2 (red, white, blue). With so few possible values, count each one, then overwrite the array in order. No comparisons at all. Trigger: "values only 0, 1, 2".
Sort the intervals by start. Then every interval that overlaps the last merged one can be absorbed in a single left-to-right sweep. Trigger: "merge intervals", "overlapping".
n is the number of elements, k is the size of the value range (max_val + 1). The last column fills in when a run on the bench finishes.
| Algorithm | Best | Average | Worst | Space | Stable | Last run on the bench |
|---|---|---|---|---|---|---|
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes | not run yet |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | not run yet |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) stack | No | not run yet |
| Bucket (counting) | O(n + k) | O(n + k) | O(n + k) | O(k) | n/a | not run yet |
Python sort() | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Timsort: merge + insertion |
Merge sort halves the array until pieces have one element, which takes log₂ n levels (3 levels for 8 elements). Each merge level touches all n elements once. n work per level × log n levels = n log n. Quick sort does the same on average, but if the pivot is always the smallest or largest value (try it on Sorted input), each level only removes one element and it degrades to n levels, O(n²).
A stable sort keeps equal values in their original order. On the bench, duplicates are tagged a, b in the order they started. That matters when you sort records by one field and want ties to keep an earlier order, for example sorting people by age after sorting them by name. Counting sort as written rebuilds the values from counts, so the original items are not kept at all.
Lift the next element, shift bigger ones right, drop it into the gap.
"Split the array in half, sort each half by recursion, then merge the two sorted halves."
Smaller values go left of the pivot, larger right; the pivot is now final. Repeat on each side.
"Count how many times each value appears, then walk the values in order and write each one back that many times."
In most problems, just call sort() and say O(n log n).
When values fall in a small range, counting beats comparing: O(n + k).
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
def merge(a, b):
res, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
res.append(a[i])
i += 1
else:
res.append(b[j])
j += 1
return res + a[i:] + b[j:]
def bucket_sort(arr, max_val):
# 1. Count: one bucket per possible value, 0..max_val
counts = [0] * (max_val + 1)
for x in arr:
counts[x] += 1
# 2. Overwrite: write each value back as many times as it was counted
i = 0
for val in range(len(counts)):
for _ in range(counts[val]):
arr[i] = val
i += 1
return arr
print(bucket_sort([2, 0, 2, 1, 1, 0], 2)) # [0, 0, 1, 1, 2, 2]
print(bucket_sort([5, 3, 0, 3, 1], 5)) # [0, 1, 3, 3, 5]
nums.sort() # in place, O(n log n)
pairs.sort(key=lambda p: p[0]) # sort by first element