Sorting Algorithms

Why learn sorts if the library sorts for you?

In practice you'll call sort() 99% of the time. But:

1. Sorting is the most common preprocessing step. Once data is sorted you can use two pointers, binary search, greedy sweeps, and deduplicate by comparing neighbours.
2. The ideas inside sorts (partitioning, merging, heaps, counting) solve many other problems — quickselect, inversion counting, Dutch flag, top-k.
3. Interviewers do ask you to implement one, or to explain complexity and stability.

Overview

Stability means equal keys keep their original relative order. It matters when you sort by multiple keys in passes (sort by name, then stable-sort by age → ties in age stay sorted by name). Python's sorted and Java's object sort are stable (Timsort); C++ sort is not — use stable_sort.

Try the sorting visualizer to watch each one.

The simple sorts

Insertion sort

Build a sorted prefix; insert each new element by shifting larger elements right.

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

void insertionSort(vector<int>& a) {
    for (int i = 1; i < (int)a.size(); i++) {
        int x = a[i], j = i - 1;
        while (j >= 0 && a[j] > x) { a[j + 1] = a[j]; j--; }
        a[j + 1] = x;
    }
}

O(n) on nearly sorted input — which is why real-world sorts (Timsort, introsort) switch to insertion sort for small subarrays.

Selection and bubble sort

Selection sort repeatedly picks the minimum of the unsorted suffix. Bubble sort repeatedly swaps adjacent out-of-order pairs. Both O(n²); know them by name, rarely use them.

Merge sort

Split in half, sort each half, merge. Covered with code in Recursion & Divide and Conquer. Key facts:

• Always O(n log n), stable, O(n) extra memory.
• The best sort for linked lists (no random access needed, merge is O(1) extra space).
• The merge step can count cross pairs (inversions, reverse pairs, range sums).

Quicksort

Pick a pivot, partition so smaller elements are left and larger are right, recurse on both sides.

import random

def quicksort(a, lo=0, hi=None):
    if hi is None:
        hi = len(a) - 1
    if lo >= hi:
        return
    p = random.randint(lo, hi)         # random pivot avoids O(n²) on sorted input
    a[p], a[hi] = a[hi], a[p]
    pivot, i = a[hi], lo
    for j in range(lo, hi):            # Lomuto partition
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[hi] = a[hi], a[i]          # pivot lands at its final index i
    quicksort(a, lo, i - 1)
    quicksort(a, i + 1, hi)

void quicksort(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int p = lo + rand() % (hi - lo + 1);
    swap(a[p], a[hi]);
    int i = lo;
    for (int j = lo; j < hi; j++)
        if (a[j] < a[hi]) swap(a[i++], a[j]);
    swap(a[i], a[hi]);
    quicksort(a, lo, i - 1);
    quicksort(a, i + 1, hi);
}

3-way partition (Dutch National Flag)

Partition into < pivot, == pivot, > pivot in one pass. This is exactly Sort Colors.

def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1
    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1; mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1              # don't advance mid: the swapped-in value is unchecked

void sortColors(vector<int>& nums) {
    int low = 0, mid = 0, high = nums.size() - 1;
    while (mid <= high) {
        if (nums[mid] == 0) swap(nums[low++], nums[mid++]);
        else if (nums[mid] == 1) mid++;
        else swap(nums[mid], nums[high--]);
    }
}

Heap sort

Build a max-heap in O(n), then repeatedly swap the root to the end and sift down. O(n log n) guaranteed, O(1) extra space, not stable. See Heaps for the sift-down routine.

Linear-time sorts

Counting sort

When values are integers in a small range [0, k), count occurrences and rebuild.

def counting_sort(a, k):
    count = [0] * k
    for x in a:
        count[x] += 1
    out = []
    for v in range(k):
        out.extend([v] * count[v])
    return out

Use it whenever the value range is small: letters (26), ages (≤150), scores (≤100), or when values are bounded by n (H-Index: citations above n can be capped at n).

Radix sort

Sort by each digit from least significant to most, using a stable counting sort per digit. O(d·(n + b)) for d digits in base b.

Bucket sort / pigeonhole

Spread values into buckets by range, sort each bucket. The pigeonhole principle trick in Maximum Gap: with n numbers across range R, some adjacent gap is at least R/(n−1), so the answer lies between buckets of that width — you only need each bucket's min and max.

Custom comparators

Most "sorting" interview problems are really about choosing the right order.

# sort by length, then alphabetically
words.sort(key=lambda w: (len(w), w))

# descending by score, ascending by name
people.sort(key=lambda p: (-p.score, p.name))

# comparator that isn't a simple key (Largest Number)
from functools import cmp_to_key
def cmp(a, b):
    return -1 if a + b > b + a else (1 if a + b < b + a else 0)
nums_as_str.sort(key=cmp_to_key(cmp))

// sort by length, then alphabetically
sort(words.begin(), words.end(), [](const string& a, const string& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
});

// Largest Number
sort(strs.begin(), strs.end(), [](const string& a, const string& b) {
    return a + b > b + a;
});

Sorting as a problem-solving step

Often you sort indices or pairs so you don't lose original positions:

order = sorted(range(n), key=lambda i: nums[i])     # indices by value
pairs = sorted(zip(nums, range(n)))                 # (value, original index)

Common mistakes

• Forgetting sorting costs O(n log n) — it can be the bottleneck.
• Sorting destroys original indices; keep them in pairs if the answer needs positions.
• Non-strict comparators in C++.
• Quicksort without randomization on sorted/adversarial input → O(n²) TLE.
• Sorting strings of numbers lexicographically ("10" < "9") when you meant numerically.