Fundamental Sorting Algorithms

Mastery target: Level A recognition progressing toward Level B implementation. You should be able to choose a sorting family from the input constraints, prove the key invariant, and explain the stability, memory, and complexity tradeoffs.

1. Problem and Motivation

Sorting rearranges records into a chosen order so later work becomes easier. Binary search needs sorted data; databases use ordered indexes for range scans; schedulers sort by deadlines; analytics pipelines sort timestamps and scores. The algorithm is rarely the whole decision. We also need to ask whether records carry equal-key identities, whether memory is limited, whether values are integers in a narrow range, and whether the data arrives almost sorted.

The same input can favor different algorithms. A tiny nearly sorted list may reward insertion sort. A large general-purpose array may use an introspective hybrid. A bounded integer key range may make counting or radix sort faster than comparison sorting. The goal is not to memorize one “best” sort; it is to recognize the assumptions each method exploits.

2. Prerequisites and Definitions

This lesson assumes arrays, loops, recursion, comparisons, and the complexity vocabulary from the previous algorithm-analysis lesson.

In-place: uses $O(1)$ or small auxiliary memory beyond the input, ignoring the recursion stack where stated.
Stable: equal-key records preserve their original relative order.
Adaptive: performance improves when the input already contains useful order.
Comparison sort: learns ordering only by comparing keys. Its general lower bound is $\Omega(n\log n)$ comparisons.
Non-comparison sort: uses key structure, digits, buckets, or direct addressing to avoid the comparison model.
Key range: the numeric or symbolic domain of values, often written as $k$ or $R$, which may dominate memory and runtime.

3. A Small Concrete Example

Worked Example

Sort four values

For [5, 2, 4, 1], insertion sort starts with the sorted prefix [5]. Insert 2 before 5, then insert 4 between 2 and 5, then insert 1 at the front.

Pass	Next value	Sorted prefix after insertion	Shift work
1	2	[2, 5]	Move 5 right
2	4	[2, 4, 5]	Move 5 right
3	1	[1, 2, 4, 5]	Move 5, 4, and 2 right

This example exposes a reusable invariant: before each insertion, the prefix to the left of the current element is already sorted. Other algorithms use different invariants, but every correct sort maintains some relationship between processed and unprocessed data.

4. Brute Force and the Core Insight

The simplest correct approach is repeated selection: scan the remaining input, find its minimum, and append it to the output. This is selection sort in its most direct form. It is easy to prove, but it performs $\Theta(n^2)$ comparisons regardless of whether the input is already sorted.

Every improvement changes what information is reused. Insertion sort reuses the sorted prefix. Merge sort reuses the fact that two halves are sorted. Quicksort reuses a partition around a pivot. Heap sort reuses the heap order. Counting, radix, and bucket sort reuse properties of the keys instead of comparing every pair.

Core insight: choose a sorting strategy by identifying the structure available in the input: existing order, balanced partitions, heap order, small integer range, digit representation, or a useful distribution.

5. Comparison Sorting Algorithms

Comparison sorts are general because they work for arbitrary comparable keys. Their tradeoff is the comparison-model lower bound: in the worst case, a comparison decision tree needs $\Omega(n\log n)$ leaves-depth work for sorting.

Bubble Sort

Bubble sort repeatedly compares adjacent values and swaps an inverted pair. Large values “bubble” toward the end. It is stable and in-place, and an early-exit flag makes it adaptive for already sorted input. Its worst-case time remains $O(n^2)$, so it is mainly useful for teaching invariants and tiny inputs.

Insertion Sort

Insertion sort grows a sorted prefix by shifting larger values right and inserting the next value into its position. It is stable, in-place, and adaptive: its time is $O(n+d)$ where $d$ is the number of inversions, with $O(n^2)$ worst-case time and $O(n)$ best-case time.

Selection Sort

Selection sort chooses the minimum remaining value and swaps it into the next output position. It performs $\Theta(n^2)$ comparisons but only $O(n)$ swaps, which can matter when writes are expensive. The basic swap version is not stable.

Merge Sort

Merge sort divides the array into halves, recursively sorts each half, and merges two sorted runs. Its recurrence is $T(n)=2T(n/2)+O(n)$, giving $O(n\log n)$ time in every case. The standard array version uses $O(n)$ auxiliary memory and is stable.

Quicksort

Quicksort chooses a pivot, partitions values into lower and higher regions, then recursively sorts those regions. Balanced partitions give expected $O(n\log n)$ time; repeatedly choosing a poor pivot produces $O(n^2)$. Randomized pivots or median-of-three selection reduce pathological exposure. In-place partitioning uses $O(\log n)$ expected recursion stack space, but the basic algorithm is not stable.

Heap Sort

Heap sort builds a max-heap, repeatedly moves its maximum to the end, and restores the heap. Heap construction is $O(n)$, each extraction costs $O(\log n)$, and total time is $O(n\log n)$ in every case. It is in-place but not stable.

6. Non-Comparison Sorting Algorithms

These algorithms can beat the comparison lower bound because they inspect key representation or use direct placement. Their complexity depends on additional parameters such as the numeric range $R$, number of digits $d$, or number of buckets $b$.

Counting Sort

Counting sort counts each integer key, computes cumulative positions, and places values into output slots. It is stable when placement scans the input from right to left. Its time and auxiliary space are $O(n+R)$, so it is excellent for a small dense range and wasteful when $R$ is huge.

Radix Sort

Radix sort processes digits from least significant to most significant, using a stable inner sort such as counting sort. For $d$ digits and base $b$, the common LSD form costs $O(d(n+b))$. It is stable if every digit pass is stable, and it is useful for fixed-width integers, identifiers, and strings with a suitable digit order.

Bucket Sort

Bucket sort distributes values into intervals, sorts each bucket, and concatenates them. With a distribution close to uniform, expected time approaches $O(n+b)$ plus the cost of local bucket sorting. Skewed data can put most values in one bucket and degrade to the local sort's worst case.

7. Practical Variants and Smaller Sorts

The remaining curriculum algorithms are valuable because they expose different engineering tradeoffs, even when they are not the default production choice.

Shell sort: performs insertion-sort passes over decreasing gaps. It is in-place and often much faster than plain insertion sort, but its exact complexity depends on the gap sequence and its stability is not guaranteed.
Comb sort: generalizes bubble sort by comparing elements separated by a shrinking gap, removing small values near the end faster than adjacent swaps.
Cocktail shaker sort: bubbles in both directions, moving large values right and small values left in each round. It remains $O(n^2)$ worst-case and is stable with adjacent swaps.
Gnome sort: walks forward when adjacent values are ordered and steps backward after a swap. It is a simple insertion-like teaching algorithm with $O(n^2)$ worst-case time.
Cycle sort: places each value directly into its final cycle position and minimizes writes, making it useful when writes have unusually high cost. It uses $O(1)$ extra space but performs $O(n^2)$ comparisons.
Pigeonhole sort: creates one hole for each value in a dense integer interval, then emits values in order. It resembles counting sort and costs $O(n+R)$ time and space.

Boundary: do not confuse stable sorting with in-place sorting. Merge sort can be stable but needs extra memory; heap sort can be in-place but is not stable. These are independent properties.

8. Correctness and Dry Run

Insertion Sort Invariant

Initialization: before the first pass, a one-element prefix is sorted.
Maintenance: insert the next value into its correct position, preserving that the expanded prefix is sorted.
Termination: when every value has been inserted, the whole array is sorted.

For merge sort, correctness follows from induction on subarray length: the base case of one value is sorted, the recursive halves are sorted by induction, and the merge procedure always chooses the smallest remaining head, so the combined result is sorted.

Partition Trace

For quicksort on [7, 2, 9, 4, 1] with pivot 4, partitioning produces values less than 4 on the left and values greater than 4 on the right. Once 4 is placed between those regions, no future recursive call needs to move it. This is the partition invariant: every value left of the pivot is no greater than it, and every value right of it is no smaller.

9. Complexity and Tradeoffs

Algorithm	Best	Average	Worst	Extra space	Stable?
Bubble	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes
Insertion	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Yes
Selection	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	No
Merge	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(n)$	Yes
Quick	$O(n\log n)$	$O(n\log n)$	$O(n^2)$	$O(\log n)$ expected	No
Heap	$O(n\log n)$	$O(n\log n)$	$O(n\log n)$	$O(1)$	No
Counting	$O(n+R)$			$O(n+R)$	Yes
Radix	$O(d(n+b))$			$O(n+b)$	Yes*
Bucket	Expected $O(n+b)$			$O(n+b)$	Depends
Shell / Comb / Cocktail / Gnome	Gap- or variant-dependent; quadratic worst cases are common			$O(1)$	Usually no / variant-dependent
Cycle / Pigeonhole	Cycle: $O(n^2)$ comparisons; Pigeonhole: $O(n+R)$			$O(1)$ / $O(R)$	No / depends

*Radix sort is stable only when each digit pass is stable. The table separates the mathematical bound from practical conditions: cache locality, branch behavior, allocation, key width, and write cost can change real performance substantially.

10. Three-Language Implementation

The following widget implements six core comparison sorts with equivalent behavior in Python, C++, and Java. Each panel is independently runnable. The additional curriculum variants are summarized above so the implementation can stay focused rather than hiding the decision tradeoffs inside one oversized program.

def bubble_sort(values):
    values = values[:]
    for end in range(len(values) - 1, 0, -1):
        swapped = False
        for index in range(end):
            if values[index] > values[index + 1]:
                values[index], values[index + 1] = values[index + 1], values[index]
                swapped = True
        if not swapped:
            break
    return values

def insertion_sort(values):
    result = values[:]
    for index in range(1, len(result)):
        value = result[index]
        position = index - 1
        while position >= 0 and result[position] > value:
            result[position + 1] = result[position]
            position -= 1
        result[position + 1] = value
    return result

def merge_sort(values):
    if len(values) <= 1:
        return values[:]
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    merged = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index]); left_index += 1
        else:
            merged.append(right[right_index]); right_index += 1
    return merged + left[left_index:] + right[right_index:]

def quick_sort(values):
    if len(values) <= 1:
        return values[:]
    pivot = values[len(values) // 2]
    lower = [value for value in values if value < pivot]
    equal = [value for value in values if value == pivot]
    higher = [value for value in values if value > pivot]
    return quick_sort(lower) + equal + quick_sort(higher)

def heap_sort(values):
    result = values[:]
    size = len(result)
    def sift_down(root, limit):
        while True:
            child = 2 * root + 1
            if child >= limit:
                return
            if child + 1 < limit and result[child] < result[child + 1]:
                child += 1
            if result[root] >= result[child]:
                return
            result[root], result[child] = result[child], result[root]
            root = child
    for root in range(size // 2 - 1, -1, -1):
        sift_down(root, size)
    for end in range(size - 1, 0, -1):
        result[0], result[end] = result[end], result[0]
        sift_down(0, end)
    return result

sample = [5, 2, 4, 1, 3]
for name, algorithm in [("bubble", bubble_sort), ("insertion", insertion_sort), ("merge", merge_sort), ("quick", quick_sort), ("heap", heap_sort)]:
    print(name, algorithm(sample))

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

std::vector<int> bubbleSort(std::vector<int> values) {
    for (int end = static_cast<int>(values.size()) - 1; end > 0; --end) {
        bool swapped = false;
        for (int index = 0; index < end; ++index) {
            if (values[index] > values[index + 1]) {
                std::swap(values[index], values[index + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
    return values;
}

std::vector<int> insertionSort(std::vector<int> values) {
    for (std::size_t index = 1; index < values.size(); ++index) {
        int value = values[index];
        std::size_t position = index;
        while (position > 0 && values[position - 1] > value) {
            values[position] = values[position - 1];
            --position;
        }
        values[position] = value;
    }
    return values;
}

std::vector<int> mergeSort(const std::vector<int>& values) {
    if (values.size() <= 1) return values;
    std::size_t middle = values.size() / 2;
    std::vector<int> left(values.begin(), values.begin() + middle);
    std::vector<int> right(values.begin() + middle, values.end());
    left = mergeSort(left); right = mergeSort(right);
    std::vector<int> merged;
    std::merge(left.begin(), left.end(), right.begin(), right.end(), std::back_inserter(merged));
    return merged;
}

std::vector<int> quickSort(std::vector<int> values) {
    if (values.size() <= 1) return values;
    int pivot = values[values.size() / 2];
    std::vector<int> lower, equal, higher;
    for (int value : values) {
        if (value < pivot) lower.push_back(value);
        else if (value == pivot) equal.push_back(value);
        else higher.push_back(value);
    }
    lower = quickSort(lower); higher = quickSort(higher);
    lower.insert(lower.end(), equal.begin(), equal.end());
    lower.insert(lower.end(), higher.begin(), higher.end());
    return lower;
}

std::vector<int> heapSort(std::vector<int> values) {
    std::make_heap(values.begin(), values.end());
    std::sort_heap(values.begin(), values.end());
    return values;
}

int main() {
    const std::vector<int> sample{5, 2, 4, 1, 3};
    for (const auto& value : heapSort(sample)) std::cout << value << ' ';
    std::cout << '\n';
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class FundamentalSorting {
    static int[] insertionSort(int[] input) {
        int[] values = input.clone();
        for (int index = 1; index < values.length; index++) {
            int value = values[index];
            int position = index - 1;
            while (position >= 0 && values[position] > value) {
                values[position + 1] = values[position];
                position--;
            }
            values[position + 1] = value;
        }
        return values;
    }

    static int[] mergeSort(int[] input) {
        if (input.length <= 1) return input.clone();
        int middle = input.length / 2;
        int[] left = Arrays.copyOfRange(input, 0, middle);
        int[] right = Arrays.copyOfRange(input, middle, input.length);
        left = mergeSort(left); right = mergeSort(right);
        int[] merged = new int[input.length];
        int leftIndex = 0, rightIndex = 0, output = 0;
        while (leftIndex < left.length && rightIndex < right.length) {
            if (left[leftIndex] <= right[rightIndex]) merged[output++] = left[leftIndex++];
            else merged[output++] = right[rightIndex++];
        }
        while (leftIndex < left.length) merged[output++] = left[leftIndex++];
        while (rightIndex < right.length) merged[output++] = right[rightIndex++];
        return merged;
    }

    static int[] heapSort(int[] input) {
        int[] values = input.clone();
        for (int root = values.length / 2 - 1; root >= 0; root--) siftDown(values, root, values.length);
        for (int end = values.length - 1; end > 0; end--) {
            int temporary = values[0]; values[0] = values[end]; values[end] = temporary;
            siftDown(values, 0, end);
        }
        return values;
    }

    static void siftDown(int[] values, int root, int limit) {
        while (2 * root + 1 < limit) {
            int child = 2 * root + 1;
            if (child + 1 < limit && values[child] < values[child + 1]) child++;
            if (values[root] >= values[child]) return;
            int temporary = values[root]; values[root] = values[child]; values[child] = temporary;
            root = child;
        }
    }

    public static void main(String[] args) {
        int[] sample = {5, 2, 4, 1, 3};
        System.out.println(Arrays.toString(insertionSort(sample)));
        System.out.println(Arrays.toString(mergeSort(sample)));
        System.out.println(Arrays.toString(heapSort(sample)));
    }
}

11. Applications and Alternatives

Choose by workload

Nearly sorted records: insertion sort can exploit a small inversion count.
Stable database records: merge sort or a stable hybrid preserves equal-key order.
Memory-constrained arrays: heap sort provides a worst-case $O(n\log n)$ bound with constant auxiliary space.
Fixed-width integers: radix sort can avoid comparison overhead.
Small dense key ranges: counting or pigeonhole sort can be linear in $n+R$.

Use comparison sorting when keys are general objects or the range is unknown. Use counting, radix, or pigeonhole sorting when key representation is cheap to inspect and the range or digit width is controlled. Use bucket sort when a distribution assumption is defensible. Stability matters when sorting records repeatedly by different fields.

For production systems, compare these fundamentals with hybrid algorithms such as Timsort and introsort. Timsort combines runs and insertion sort for real-world partially ordered data; introsort begins like quicksort but switches to heap sort when recursion indicates a bad partition pattern.

12. Exercises and Mastery

Easy

Trace bubble sort on [4, 1, 3, 2] and mark the largest value after each pass.
Implement insertion sort and state its sorted-prefix invariant.
Classify each listed algorithm as comparison or non-comparison sorting.

Medium

Implement stable counting sort for records keyed by an integer field.
Compare merge sort, heap sort, and quicksort for stable output, memory, and worst-case guarantees.
Choose a gap sequence for shell sort and measure it against insertion sort on nearly sorted inputs.

Hard

Prove the $O(n\log n)$ expected time of randomized quicksort using the expected partition recurrence.
Design an LSD radix sort for fixed-width signed integers and explain how negative values are handled.
Construct an adversarial input for bucket sort and explain why its distribution assumption fails.

Mastery challenge: A service sorts millions of records by a 32-bit integer key. Records with equal keys must retain arrival order, memory is limited, and the input is often nearly sorted. Choose a strategy, justify the choice, state the worst-case behavior, and explain what you would benchmark before shipping.

Review rhythm: tomorrow, reconstruct insertion, merge, quick, and heap sort from the invariants; next week, implement the comparison and non-comparison families in Python, C++, and Java; several weeks later, choose a sorting method for an unfamiliar workload without being told the intended algorithm.

13. Summary Cheat Sheet

Bubble, insertion, selection, merge, quick, and heap sort are comparison-based fundamentals.
Counting, radix, bucket, and pigeonhole sort exploit key structure and can avoid the comparison lower bound.
Shell, comb, cocktail, gnome, and cycle sort are useful variants for understanding gaps, locality, adaptiveness, or write cost.
Insertion sort is excellent for small or nearly sorted data; merge sort is stable with predictable $O(n\log n)$ time.
Quicksort is fast on average but needs pivot protection; heap sort gives a worst-case bound with low extra memory.
Stability, in-place behavior, key range, digit width, distribution, and write cost are separate tradeoffs.