Sorting — Selection, Bubble, Insertion, Merge Sort and Quicksort

Vocabulary

Selection sort

Repeatedly select the minimum of the unsorted suffix and swap it to the front.

def selection_sort(a):
    n = len(a)
    for i in range(n - 1):
        m = i
        for j in range(i + 1, n):
            if a[j] < a[m]:
                m = j
        a[i], a[m] = a[m], a[i]
    return a

• Comparisons: always $\frac{n(n-1)}{2}$. Swaps: at most $n - 1$ (the fewest of any simple sort — useful when writes are expensive).
• $\Theta(n^2)$ in every case; in place; not stable; not adaptive.

Bubble sort

Sweep left to right, swapping adjacent out-of-order pairs; after pass $k$ the $k$ largest elements are in their final places.

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:          # early exit: makes the best case O(n)
            break
    return a

• Swaps = number of inversions. Comparisons: worst $\frac{n(n-1)}{2}$; best $n - 1$ with the early-exit flag.
• In place, stable, adaptive (with the flag). Rarely the right choice in practice.

Insertion sort

Grow a sorted prefix; insert each new element into place by shifting larger elements right.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]      # shift
            j -= 1
        a[j + 1] = key
    return a

• Shifts = inversions; comparisons between $n - 1$ (sorted) and $\frac{n(n-1)}{2}$ (reversed).
• Best $O(n)$, average and worst $O(n^2)$; in place, stable, adaptive; excellent for small or nearly sorted arrays, which is why hybrid sorts (Timsort, introsort) use it for small runs.

Merge sort (divide and conquer)

Split in half, sort each half recursively, merge the two sorted halves.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:          # <= keeps it stable
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

• $T(n) = 2T(n/2) + \Theta(n) = \Theta(n\log n)$ in every case; at most $n\lceil\log_2 n\rceil$ comparisons.
• Merging lists of sizes $m$ and $n$: between $\min(m, n)$ and $m + n - 1$ comparisons.
• Needs $O(n)$ extra space for arrays (not in place); stable; ideal for linked lists and external sorting of data that doesn't fit in memory.

Quicksort (divide and conquer)

Choose a pivot, partition the array into elements ≤ pivot and > pivot, then recursively sort both sides. All the work is in partitioning; there is no merge step.

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo < hi:
        p = partition(a, lo, hi)      # Lomuto: pivot = a[hi]
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)
    return a

• Lomuto partition (pivot = last element) is simple; Hoare partition (two pointers moving inward) does about three times fewer swaps.
• Best/average: $\Theta(n\log n)$ (about $1.39\,n\log_2 n$ comparisons on average). Worst: $\Theta(n^2)$ when the pivot is always the smallest or largest — e.g. sorted input with first/last-element pivots, or all-equal keys with a naive partition.
• In place ($O(\log n)$ stack expected, $O(n)$ worst unless you recurse on the smaller side first); not stable; usually the fastest in practice thanks to cache-friendly scanning.
• Fixes for bad pivots: random pivot, median-of-three, three-way partitioning for duplicates; introsort switches to heapsort when recursion gets too deep.

Lower bound and non-comparison sorts

Any comparison sort corresponds to a binary decision tree with at least $n!$ leaves, so the worst case needs at least $\lceil\log_2 n!\rceil = \Omega(n\log n)$ comparisons (e.g. at least 3 comparisons for 3 elements, 5 for 4 elements).

Counting sort ($O(n + k)$ for keys in $0..k$), radix sort and bucket sort avoid comparisons and can run in linear time for suitable keys.

Which sort?

Quick revision