Sorting
Algorithms

Sorting is everywhere

Sorting is the most fundamental algorithmic problem in computer science. Efficient sorting enables efficient searching, merging, and data presentation.

• Database ORDER BY clauses execute a sort
• Binary search requires sorted input — O(log n) vs O(n)
• Merge operations (joins, set intersection) assume sorted streams
• Rendering leaderboards, timelines, search results
• Scheduling, priority queues, and resource allocation

What we will cover

Repeatedly swap adjacent elements if they are in the wrong order. The largest unsorted element "bubbles up" to its correct position each pass.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:
            break  # already sorted

Properties

Find the minimum element in the unsorted region and swap it into the next position of the sorted region. Exactly n - 1 swaps — minimal writes.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

Properties

Build a sorted sub-array one element at a time by inserting each new element into its correct position. The way most people sort a hand of playing cards.

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]
            j -= 1
        arr[j + 1] = key

Properties

Divide the array in half, recursively sort each half, then merge the two sorted halves. The canonical divide-and-conquer sorting algorithm.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(L, R):
    result = []
    i = j = 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]:
            result.append(L[i]); i += 1
        else:
            result.append(R[j]); j += 1
    result.extend(L[i:])
    result.extend(R[j:])
    return result

Properties

Choose a pivot, partition the array so all elements less than the pivot come before it and all greater come after, then recursively sort the partitions.

def quicksort(arr, lo, hi):
    if lo < hi:
        p = partition(arr, lo, hi)
        quicksort(arr, lo, p - 1)
        quicksort(arr, p + 1, hi)

def partition(arr, lo, hi):
    pivot = arr[hi]
    i = lo - 1
    for j in range(lo, hi):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
    return i + 1

Properties

Build a max-heap from the input, then repeatedly extract the maximum element and place it at the end of the array. Uses the heap property to maintain order.

def heap_sort(arr):
    n = len(arr)
    # Build max-heap
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

def heapify(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

Properties

Three steps

Merge Sort vs Quick Sort

The decision-tree argument

Any comparison-based sorting algorithm can be modelled as a binary decision tree, where each internal node is a comparison and each leaf is a permutation of the input.

• For n elements there are n! possible permutations
• The tree must have at least n! leaves
• A binary tree with L leaves has height at least log2 L
• Therefore: height ≥ log2(n!)
• By Stirling's approximation: log2(n!) = Ω(n log n)

Decision tree for 3 elements

Count occurrences of each key value, compute prefix sums, then place elements directly into their final positions. No comparisons needed.

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    output = [0] * len(arr)

    for x in arr:
        count[x] += 1
    for i in range(1, max_val + 1):
        count[i] += count[i - 1]

    # Traverse in reverse for stability
    for x in reversed(arr):
        output[count[x] - 1] = x
        count[x] -= 1
    return output

Properties

Sort integers digit by digit, from least significant to most significant (LSD) or vice versa (MSD). Uses a stable sub-sort (typically counting sort) at each digit position.

def radix_sort(arr):
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    while max_val // exp > 0:
        counting_sort_by_digit(arr, exp)
        exp *= 10

def counting_sort_by_digit(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    for x in arr:
        idx = (x // exp) % 10
        count[idx] += 1
    for i in range(1, 10):
        count[i] += count[i - 1]
    for x in reversed(arr):
        idx = (x // exp) % 10
        output[count[idx] - 1] = x
        count[idx] -= 1
    arr[:] = output

Properties

Distribute elements into buckets based on their value, sort each bucket individually (often with insertion sort), then concatenate the buckets.

def bucket_sort(arr):
    if not arr:
        return arr
    n = len(arr)
    buckets = [[] for _ in range(n)]
    min_val, max_val = min(arr), max(arr)
    spread = max_val - min_val or 1

    for x in arr:
        idx = int((x - min_val) / spread * (n - 1))
        buckets[idx].append(x)

    for bucket in buckets:
        insertion_sort(bucket)

    return [x for bucket in buckets for x in bucket]

Properties

Parallel sorting

Modern hardware has many cores. Sorting algorithms can exploit parallelism to achieve significant speedups.

External sorting

When data exceeds available RAM, we sort in chunks that fit in memory, write sorted "runs" to disk, then merge the runs.

Cache and memory effects

• Asymptotic complexity ignores constant factors and cache behaviour
• Quicksort's sequential access pattern is cache-friendly — data in the same partition stays in L1/L2 cache
• Heapsort's parent/child jumps cause frequent cache misses
• Merge sort's auxiliary array doubles memory footprint — relevant when n is large
• For linked lists, merge sort is ideal (no random access needed, O(1) extra space)

Language and API considerations

• Python list.sort() is Timsort — stable, O(n log n). Use key= parameter for custom comparisons, not cmp
• C++ std::sort is Introsort — unstable. Use std::stable_sort when stability matters
• Java Arrays.sort uses Timsort for objects (stable) and dual-pivot quicksort for primitives (faster, no stability needed)
• Always prefer built-in sorts over hand-rolled implementations — they are tuned, tested, and optimised for the runtime

Key takeaways

• Comparison sorts have a fundamental lower bound of Ω(n log n) — merge sort and heap sort are asymptotically optimal
• Non-comparison sorts (counting, radix, bucket) bypass this limit by exploiting key structure
• No single sort wins on every metric — stability, memory, adaptivity, and cache behaviour all matter
• Insertion sort is the best quadratic sort and is used as a sub-routine in all major hybrid algorithms
• Real-world sorts are hybrids: Timsort (merge + insertion), Introsort (quick + heap + insertion), pdqsort (quicksort + heap + insertion + pattern detection)
• Use your language's built-in sort unless profiling reveals a specific bottleneck
• External merge sort handles data larger than memory
• Understanding sorting deeply improves your ability to reason about algorithmic trade-offs in general

Recommended reading