Sorting

No. 04 · SVG · Type caseinsertion · merge · quick · bucket · stability

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.

Step 1 / 1
READY
Comparisons
Moves
Extra space
Stable?
Codeinsertion_sort.py
Code
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

Examples

Bucket sort · LeetCode 75

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".

O(n) timeO(1) spaceone counting pass and one writing pass; only 3 counters
Sort first · LeetCode 56

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".

O(n log n) timeO(n) spacethe sort dominates; the sweep is O(n); the result can hold n intervals

Time and space: the four sorts side by side

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.

AlgorithmBestAverageWorstSpaceStableLast run on the bench
InsertionO(n)O(n²)O(n²)O(1)Yesnot run yet
MergeO(n log n)O(n log n)O(n log n)O(n)Yesnot run yet
QuickO(n log n)O(n log n)O(n²)O(log n) stackNonot run yet
Bucket (counting)O(n + k)O(n + k)O(n + k)O(k)n/anot run yet
Python sort()O(n)O(n log n)O(n log n)O(n)YesTimsort: merge + insertion

Where n log n comes from

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²).

What "stable" means

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.

How to remember them

Insertion: lift, shift, drop

Lift the next element, shift bigger ones right, drop it into the gap.

Merge: split, sort, merge

"Split the array in half, sort each half by recursion, then merge the two sorted halves."

Quick: pivot, partition, recurse

Smaller values go left of the pivot, larger right; the pivot is now final. Repeat on each side.

Bucket: count, overwrite

"Count how many times each value appears, then walk the values in order and write each one back that many times."

Trigger words: when the problem wants sorting

Sort first

  • sort
  • order
  • merge intervals

In most problems, just call sort() and say O(n log n).

Bucket sort

  • values only 0, 1, 2
  • Sort Colors
  • small fixed range

When values fall in a small range, counting beats comparing: O(n + k).

Template

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