Sorting Algorithms

Sorting is one of the most studied problems in computer science. Understanding the major algorithms — not just how to call a sort function, but how sorting works — teaches recursion, divide-and-conquer, and the concept of theoretical lower bounds.

The Comparison Lower Bound

Before diving into algorithms, a fundamental result: any algorithm that sorts by comparing elements requires at least O(n log n) comparisons in the worst case.

The argument: there are n! possible orderings of n elements. Each comparison eliminates some orderings. A binary decision tree of comparisons must have at least n! leaves — and a binary tree with n! leaves has height at least log₂(n!) ≈ n log n (by Stirling's approximation). No comparison sort can beat this.

This means merge sort, heapsort, and Timsort are theoretically optimal for comparison sorting.

Bubble Sort — O(n²)

Repeatedly steps through the list, compares adjacent elements, and swaps them if out of order. After each pass, the largest unsorted element "bubbles" to its correct position.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

• Time: O(n²) worst and average; O(n) best (already sorted, with early-exit optimisation)
• Space: O(1) — in-place
• Use when: never in production. Useful for teaching the concept of swapping adjacent elements.

Insertion Sort — O(n²)

Builds the sorted array one element at a time by inserting each new element into its correct position among the already-sorted elements.

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
    return arr

• Time: O(n²) worst; O(n) best (already sorted)
• Space: O(1) — in-place
• Use when: the array is small (n < 20) or nearly sorted. Timsort uses insertion sort for small runs.

Merge Sort — O(n log n)

Divide-and-conquer: split the array in half recursively until each piece has one element, then merge pairs of sorted pieces back together.

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(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Why O(n log n)? The array is split log n times. Each merge level processes all n elements total. Total work: n × log n.

• Time: O(n log n) in all cases — guaranteed
• Space: O(n) — needs auxiliary arrays for merging
• Stable: yes — equal elements preserve their original order
• Use when: stable sort is required, or working with linked lists (in-place merge is possible for linked lists)

Quick Sort — O(n log n) average

Choose a pivot element. Partition the array so all elements smaller than the pivot are to its left, all larger to its right. Recursively sort each partition.

def quick_sort(arr, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low < high:
        pivot_idx = partition(arr, low, high)
        quick_sort(arr, low, pivot_idx - 1)
        quick_sort(arr, pivot_idx + 1, high)
    return arr

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

• Time: O(n log n) average; O(n²) worst case (sorted input with bad pivot choice)
• Space: O(log n) stack space; O(1) extra for in-place partitioning
• Stable: no
• Use when: average-case performance matters and memory is limited. Real implementations use random pivot selection to avoid worst-case O(n²).

Why quicksort beats mergesort in practice despite the same Big O? Cache efficiency. Quicksort operates in-place, accessing sequential memory. Mergesort allocates separate arrays, causing more cache misses. The constant factor matters in practice.

Heap Sort — O(n log n)

Build a max-heap from the array, then repeatedly extract the maximum element and place it at the end.

import heapq

def heap_sort(arr):
    # Python's heapq is a min-heap, so negate for max-heap
    heap = [-x for x in arr]
    heapq.heapify(heap)                    # O(n)
    return [-heapq.heappop(heap) for _ in arr]   # O(n log n)

• Time: O(n log n) guaranteed
• Space: O(1) — in-place (with direct heap manipulation)
• Stable: no
• Use when: guaranteed O(n log n) with O(1) space is required (rarely chosen over Timsort in practice)

Counting Sort and Radix Sort — O(n + k)

When values fall within a bounded range, you can beat the O(n log n) lower bound by not comparing elements.

Counting sort: count how many times each value appears, then reconstruct the sorted array.

def counting_sort(arr, max_val):
    count = [0] * (max_val + 1)
    for x in arr:
        count[x] += 1
    result = []
    for val, freq in enumerate(count):
        result.extend([val] * freq)
    return result

• Time: O(n + k) where k = range of values
• Space: O(k)
• Use when: values are integers in a known, small range

Algorithm Comparison

What Python's sorted() Uses

Python's built-in sort is Timsort — a hybrid of merge sort and insertion sort. It detects naturally ordered runs in the data, sorts small runs with insertion sort (efficient for nearly-sorted data), and merges them with merge sort. It is stable and guaranteed O(n log n). For almost all practical purposes, use the built-in.

Key Takeaways

• No comparison-based sort can beat O(n log n) — this is a mathematical lower bound.
• Merge sort is O(n log n) guaranteed and stable, at the cost of O(n) extra space.
• Quicksort is faster in practice due to cache efficiency, but has an O(n²) worst case.
• Heapsort gives O(n log n) with O(1) space but is not stable.
• Counting sort and radix sort beat O(n log n) by avoiding comparisons — only valid for bounded integer ranges.
• In production code, use your language's built-in sort (Timsort in Python/Java). Only implement your own if you have a specific constraint it cannot satisfy.