Sorting

Sorting rearranges records by key and supports searching, deduplication, ranking, grouping, merging, and range processing. Algorithms for the same simple specification differ in stability, mutation, auxiliary memory, adaptivity, worst-case guarantees, and assumptions about keys. There is no universally best sort; the input and interface determine the appropriate one.

Sorting Properties

Sorting takes a sequence of n comparable items and rearranges them into non-decreasing order. Running time alone does not determine whether a sorting algorithm satisfies an application’s contract. Two central properties are:

• Stability: a sort is stable if it preserves the relative order of elements that compare as equal. If student records are first sorted by name and then stably sorted by grade, equal-grade records remain in name order. An unstable sort may rearrange them.
• In-place operation: an in-place sort rearranges the input with O(1) auxiliary element storage. An algorithm that needs an additional O(n) array may exceed memory limits when the input already fills most available memory.

Other relevant properties include adaptivity to existing order, worst-case guarantees, comparison versus key-index operations, and whether the algorithm mutates the input.

Elementary Sorts

Bubble, selection, and insertion sort are O(n²) in the worst case but make different numbers of swaps, react differently to existing order, and serve as useful small-input or specialized components.

The elementary C examples require n >= 0 and a non-null array whenever n > 0.

Bubble Sort

Repeatedly scan the array, swapping any adjacent pair that’s out of order. Each full pass guarantees that the largest remaining element “bubbles up” to its correct final position.

#include <stdbool.h>

void bubble_sort(int arr[], int n) {
    for (int pass = 0; pass < n - 1; pass++) {
        bool swapped = false;
        for (int i = 0; i < n - 1 - pass; i++) {
            if (arr[i] > arr[i + 1]) {
                int tmp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = tmp;
                swapped = true;
            }
        }
        if (!swapped) {
            break;                      /* nothing moved this pass: already sorted */
        }
    }
}

The swapped flag lets the algorithm detect that a complete pass made no changes. An already sorted array therefore takes Theta(n) time instead of completing all n - 1 passes.

Selection Sort

Repeatedly find the minimum of the unsorted remainder and swap it into place at the front.

void selection_sort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        if (min_idx != i) {
            int tmp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = tmp;
        }
    }
}

Selection sort makes at most n - 1 swaps regardless of input order. That bound can matter when moving a record is much more expensive than comparing two keys. It still examines the entire unsorted suffix on every pass, so its time remains Theta(n^2) on a sorted array. It is not stable: sorting [3a, 3b, 1] swaps 1 with 3a and leaves the equal records in the order 3b, 3a.

Insertion Sort

Build up the sorted region one element at a time: take the next element from the unsorted part, and slide it leftward into its correct position within the already-sorted prefix.

void insertion_sort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];        /* shift larger element rightward */
            j--;
        }
        arr[j + 1] = key;               /* drop key into the gap we made */
    }
}

Insertion sort’s movement is proportional to the number of inversions—pairs in the wrong relative order. An already sorted array has zero inversions and runs in Theta(n). Nearly sorted append-heavy data can have only O(n) inversions. This adaptivity and low overhead make insertion sort useful inside hybrid algorithms for small runs.

On [7,3,5,2,9,1], the sorted prefix after each insertion is:

[7]
[3,7]
[3,5,7]
[2,3,5,7]
[2,3,5,7,9]
[1,2,3,5,7,9]

Before each outer iteration, arr[0..i) is sorted and contains exactly the original first i items. Shifting elements larger than key opens one position without losing any item, and inserting key restores the invariant for a prefix one item longer. Each shift removes exactly one inversion involving key, so total shifts equal the input’s inversion count.

Step through those shifts and compare the array after each insertion:

The worst-case class alone hides inversion sensitivity and crossover constants. A complete comparison reports the relevant case, data order, movement cost, and input range.

Merge Sort

Merge sort splits the array, recursively sorts both halves, then merges the sorted results. The merge step determines stability, memory use, and linear work per recursion level:

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

static bool merge_ranges(int arr[], size_t lo, size_t mid, size_t hi) {
    size_t n1 = mid - lo + 1U;
    size_t n2 = hi - mid;
    if (n1 > SIZE_MAX / sizeof(int) || n2 > SIZE_MAX / sizeof(int)) {
        return false;
    }
    int *left = malloc(n1 * sizeof(*left));
    int *right = malloc(n2 * sizeof(*right));
    if (left == NULL || right == NULL) {
        free(left);
        free(right);
        return false;
    }
    for (size_t i = 0; i < n1; i++) {
        left[i] = arr[lo + i];
    }
    for (size_t j = 0; j < n2; j++) {
        right[j] = arr[mid + 1U + j];
    }

    size_t i = 0U;
    size_t j = 0U;
    size_t k = lo;
    while (i < n1 && j < n2) {
        if (left[i] <= right[j]) {      /* <=, not <, is what makes this merge STABLE */
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < n1) {
        arr[k++] = left[i++];
    }
    while (j < n2) {
        arr[k++] = right[j++];
    }

    free(left);
    free(right);
    return true;
}

static bool merge_sort_range(int arr[], size_t lo, size_t hi) {
    if (lo >= hi) {
        return true;
    }
    size_t mid = lo + (hi - lo) / 2U;
    if (!merge_sort_range(arr, lo, mid) ||
        !merge_sort_range(arr, mid + 1U, hi)) {
        return false;
    }
    return merge_ranges(arr, lo, mid, hi);
}

bool merge_sort(int arr[], size_t n) {
    if (n > 0U && arr == NULL) {
        return false;
    }
    return n < 2U || merge_sort_range(arr, 0U, n - 1U);
}

Merge sort takes Theta(n log n) time on every input order. The <= tie rule takes an equal element from the left range first and therefore preserves stability; changing it to < can reorder equal records while leaving keys sorted. The status return reports allocation or size failure.

The implementation uses O(n) peak auxiliary storage and O(log n) recursion depth. In-place stable merging exists but requires more intricate algorithms and different constant-factor tradeoffs.

Merge Trace

Suppose recursive calls have produced left=[2a,5,7] and right=[2b,3,6], where tags distinguish equal keys. The merge compares only the unconsumed front items:

The loop invariant is that arr[lo..k) contains the smallest k-lo items from the two input ranges in sorted order, and each unconsumed item is at least the last emitted item. The smaller front must be the smallest remaining item because both inputs are sorted. Emitting it preserves the invariant; exhaustion permits copying the other already-sorted suffix. Every input item is copied exactly once, proving permutation preservation. Taking 2a before 2b on equality proves stability across the split.

The status API has a weaker failure guarantee than a transaction: if allocation fails in a later recursive call, an earlier subrange may already be sorted. On false, callers must not assume the original order remains intact. Providing strong failure atomicity would require additional storage or a different top-level allocation plan.

Quicksort

Quicksort performs its main work while dividing. A partition rearranges a range around a chosen pivot. After the resulting subranges are sorted recursively, no separate merge step is needed.

Lomuto Partition

int lomuto_partition(int arr[], int lo, int hi) {
    int pivot = arr[hi];                /* choosing the last element as pivot (Lomuto scheme) */
    int i = lo - 1;                     /* boundary of the "smaller than pivot" region */
    for (int j = lo; j < hi; j++) {
        if (arr[j] < pivot) {
            i++;
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1];
    arr[i + 1] = arr[hi];
    arr[hi] = tmp;                       /* place pivot in its final position */
    return i + 1;                        /* the pivot's final index */
}

void quicksort(int arr[], int lo, int hi) {
    if (lo < hi) {
        int p = lomuto_partition(arr, lo, hi);
        quicksort(arr, lo, p - 1);
        quicksort(arr, p + 1, hi);
    }
}

The contract is 0 <= lo <= hi for a nonempty range and a valid array; calling quicksort(arr, 0, -1) represents an empty range. Lomuto places the pivot at its final index. With the strict < pivot test, an all-equal range sends every nonpivot element to one side and creates quadratic time.

Hoare Partition

Hoare’s scheme scans inward and swaps misplaced pairs. The returned index is a boundary, not necessarily the pivot’s final index, so its recursive ranges are [lo,p] and [p+1,hi]:

int hoare_partition(int arr[], int lo, int hi) {
    int pivot = arr[lo + (hi - lo) / 2];
    int i = lo;
    int j = hi;

    for (;;) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i >= j) {
            return j;
        }
        int temporary = arr[i];
        arr[i] = arr[j];
        arr[j] = temporary;
        i++;
        j--;
    }
}

void quicksort_hoare(int arr[], int lo, int hi) {
    if (lo < hi) {
        int boundary = hoare_partition(arr, lo, hi);
        quicksort_hoare(arr, lo, boundary);
        quicksort_hoare(arr, boundary + 1, hi);
    }
}

The pivot value lies inside the range, so both scans stop before leaving it. Advancing both indices after an equal-value swap guarantees progress. Hoare partition often handles duplicate-heavy input better than the shown two-way Lomuto scheme, although three-way partitioning is the stronger explicit duplicate strategy.

Duplicate Partitioning

Trace strict Lomuto partition on [4a,2,4b,1,4c] with pivot 4c. Values 2 and 1 cross the boundary; equal values 4a and 4b do not. The final swap produces [2,1,4c,4a,4b] and pivot index 2. The partition contract is satisfied—items left of the pivot are smaller and items right are at least as large—but the equal keys remain in a recursive side. On an all-equal input of length n, that side has length n-1 at every call.

A three-way partition separates keys into < pivot, == pivot, and > pivot regions in one scan:

lt = lo, i = lo, gt = hi
while i <= gt:
    if a[i] < pivot:
        swap a[lt], a[i]
        lt++, i++
    else if a[i] > pivot:
        swap a[i], a[gt]
        gt--
    else:
        i++

Its invariant partitions the range into

[lo,lt)       keys < pivot
[lt,i)        keys == pivot
[i,gt]        unclassified
(gt,hi]       keys > pivot

The greater-than branch does not increment i because the item swapped from gt has not yet been classified. After termination, quicksort recurses only on [lo,lt) and (gt,hi]; the equal region is already final. An all-equal range therefore finishes after one linear partition instead of generating a quadratic chain. This strategy is especially valuable for categorical keys and duplicate-heavy adversarial inputs.

Pivot Choice

On an already sorted array, lomuto_partition with the last element as pivot places that pivot at the end and produces subranges of sizes n - 1 and 0. The recurrence is T(n) = T(n - 1) + Theta(n), which solves to Theta(n^2).

Quicksort’s worst-case running time is Theta(n^2). If each pivot divides the current range so that neither side contains more than a fixed fraction of its elements—for example, if the pivot always lands in the middle 50%—the recursion depth is O(log n) and the total work is Theta(n log n). Under uniformly random pivot ranks, sufficiently balanced partitions occur often enough to give Theta(n log n) expected time. This distinction between adversarial and expected behavior illustrates the case-analysis methods from the Complexity chapter.

Fixed first, last, or middle positions let input order predict the pivot. Median-of-three compares the first, middle, and last keys and chooses the median of those three—not the median of the whole range. It avoids choosing an endpoint value on already sorted or reverse-sorted data, but it remains deterministic and can still be attacked by a constructed order. Random selection makes pivot rank independent of any input fixed before the random draw.

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

static bool random_index(int lo, int hi, int *index) {
    if (index == NULL || lo < 0 || hi < lo) {
        return false;
    }

    uintmax_t width = (uintmax_t) (unsigned int) (hi - lo) + 1U;
    uintmax_t sample_count = (uintmax_t) RAND_MAX + 1U;
    if (width > sample_count) {
        return false;
    }

    uintmax_t limit = sample_count - sample_count % width;
    int draw = 0;
    do {
        draw = rand();
    } while ((uintmax_t) draw >= limit);

    *index = lo + (int) ((uintmax_t) draw % width);
    return true;
}

static bool randomized_lomuto(int arr[], int lo, int hi, int *pivot) {
    int pivot_index = 0;
    if (!random_index(lo, hi, &pivot_index)) {
        return false;
    }
    int temporary = arr[pivot_index];
    arr[pivot_index] = arr[hi];
    arr[hi] = temporary;
    *pivot = lomuto_partition(arr, lo, hi);
    return true;
}

static bool randomized_quicksort_range(int arr[], int lo, int hi) {
    while (lo < hi) {
        int pivot = 0;
        if (!randomized_lomuto(arr, lo, hi, &pivot)) {
            return false;
        }
        if (pivot - lo < hi - pivot) {
            if (!randomized_quicksort_range(arr, lo, pivot - 1)) {
                return false;
            }
            lo = pivot + 1;
        } else {
            if (!randomized_quicksort_range(arr, pivot + 1, hi)) {
                return false;
            }
            hi = pivot - 1;
        }
    }
    return true;
}

bool randomized_quicksort(int arr[], int n) {
    if (n < 0 || (n > 0 && arr == NULL)) {
        return false;
    }
    if ((uintmax_t) (unsigned int) n > (uintmax_t) RAND_MAX + 1U) {
        return false;
    }
    return n < 2 || randomized_quicksort_range(arr, 0, n - 1);
}

Seed the generator once outside the sorting function. Rejection sampling avoids the modulo bias that occurs when the number of possible rand() results is not divisible by the range width. This compact implementation reports failure when the initial range has more than RAND_MAX + 1 positions; a production implementation should use a wider random source. Under independent uniform pivot ranks, expected time is Theta(n log n) and worst-case time remains Theta(n^2). Recursing only on the smaller partition and iterating over the larger one limits call-stack depth to O(log n) even in the time worst case. The C library’s rand() is not suitable for security-sensitive adversarial input.

Heapsort

Heapsort combines a Theta(n log n) worst-case bound with O(1) auxiliary element storage. A max-heap stores a complete binary tree in an array and maintains the invariant that every parent’s key is at least its children’s keys. The maximum is therefore at index 0.

The algorithm first builds a max-heap in Theta(n) time. It then swaps the root with the last element of the unsorted region, shrinks that region, and restores the heap invariant by sifting the new root downward.

#include <stddef.h>

static void sift_down(int arr[], size_t heap_size, size_t root) {
    while (root < heap_size / 2U) {
        size_t left = 2U * root + 1U;
        size_t right = left + 1U;
        size_t largest = root;

        if (arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < heap_size && arr[right] > arr[largest]) {
            largest = right;
        }
        if (largest == root) {
            return;
        }

        int temporary = arr[root];
        arr[root] = arr[largest];
        arr[largest] = temporary;
        root = largest;
    }
}

void heap_sort(int arr[], size_t n) {
    if (n < 2U) {
        return;
    }

    for (size_t i = n / 2U; i > 0U; i--) {
        sift_down(arr, n, i - 1U);
    }
    for (size_t end = n; end > 1U; end--) {
        int temporary = arr[0];
        arr[0] = arr[end - 1U];
        arr[end - 1U] = temporary;
        sift_down(arr, end - 1U, 0U);
    }
}

The contract requires a non-null array when n > 0. The first loop visits all internal nodes from right to left and bottom to top. The second loop leaves the suffix arr[end..n) sorted and final while arr[0..end) remains a max-heap. Iterative sifting keeps auxiliary space constant.

Building the heap is Theta(n), not Theta(n log n). A node at height h can sift down at most h levels, and a complete binary heap has at most about n/2^(h+1) nodes of height h. Summing the work gives

Most nodes are leaves or near leaves and do almost no work; only a few nodes can travel the full height. The extraction phase performs n-1 sifts of at most Theta(log n) each, so it supplies the overall Theta(n log n) bound.

Selection sort and heapsort both repeatedly place an extreme item at the boundary. Selection sort finds that item with a linear scan on every pass. Heapsort maintains a representation that exposes the maximum immediately and repairs itself in O(log n), reducing total time from Theta(n^2) to Theta(n log n).

Heapsort is not stable because distant swaps can reorder equal records. It also commonly has poorer cache locality than a tuned quicksort, so its stronger worst-case guarantee does not imply a lower wall-clock time on every workload.

Comparison Sorts

* The direct two-call recursive quicksort can reach Theta(n) stack depth. The randomized version above always recurses on the smaller side and therefore uses O(log n) stack space even when its running time is quadratic. “In place” refers to auxiliary element storage and does not automatically include call-stack space.

Sorting Bounds

No comparison-based sorting algorithm can guarantee o(n log n) comparisons on arbitrary distinct keys. A decision-tree argument proves the lower bound for every algorithm in the comparison model.

Any comparison sort can be modeled as a decision tree: each internal node represents one comparison (is arr[i] < arr[j]?), each branch represents one possible outcome, and each leaf represents one fully-determined output ordering. To correctly sort every possible input arrangement of n distinct elements, the tree must have at least n! leaves — one for each possible permutation, since the algorithm must be able to distinguish any one arrangement from any other and produce the right answer for each. A binary tree with L leaves must have height at least log₂ L (you cannot fit more leaves into a tree than 2^height). Therefore the height of this decision tree — which corresponds exactly to the worst-case number of comparisons the algorithm might need to make — is at least log₂(n!). Using Stirling’s approximation, log₂(n!) = Θ(n log n).

The argument assumes only pairwise comparisons and correctness on every permutation, not a particular strategy or language. It is a model-wide lower bound rather than an analysis of one implementation.

The bound applies only when ordering information is obtained through comparisons. Bounded integer keys permit direct indexing and therefore a different model.

Linear Sorts

Additional structure in the keys can support sorting without pairwise comparisons. The comparison-model Omega(n log n) lower bound then does not apply.

Counting Sort

Suppose every element is an integer between 0 and some known maximum k. Count how many times each value occurs; turn those counts into a running total (a prefix sum), which directly tells you how many elements are less than or equal to any given value — and therefore exactly which output position each element belongs in.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

bool counting_sort(int arr[], size_t n, int max_value) {
    if (max_value < 0 || (n > 0U && arr == NULL)) {
        return false;
    }
    if (n == 0U) {
        return true;
    }
    for (size_t i = 0U; i < n; i++) {
        if (arr[i] < 0 || arr[i] > max_value) {
            return false;
        }
    }

    uintmax_t range_wide = (uintmax_t) (unsigned int) max_value + 1U;
    if (range_wide > SIZE_MAX) {
        return false;
    }
    size_t range = (size_t) range_wide;
    if (range > SIZE_MAX / sizeof(size_t) ||
        n > SIZE_MAX / sizeof(int)) {
        return false;
    }

    size_t *count = calloc(range, sizeof(*count));
    int *output = malloc(n * sizeof(*output));
    if (count == NULL || output == NULL) {
        free(count);
        free(output);
        return false;
    }

    for (size_t i = 0U; i < n; i++) {
        count[(size_t) arr[i]]++;
    }
    for (size_t value = 1U; value < range; value++) {
        count[value] += count[value - 1U];
    }
    for (size_t i = n; i > 0U; i--) {
        size_t value = (size_t) arr[i - 1U];
        output[--count[value]] = arr[i - 1U];
    }
    for (size_t i = 0U; i < n; i++) {
        arr[i] = output[i];
    }

    free(count);
    free(output);
    return true;
}

The function accepts only keys in [0,max_value] and reports invalid input, impossible allocation sizes, or allocation failure. With k = max_value + 1 possible keys, its time and auxiliary space are Theta(n + k). It is linear in the input size when k = O(n), but wasteful when the numeric range is much larger than the number of records.

After the prefix-sum loop, count[v] is the number of input keys at most v. Decrementing it gives the next output index reserved for v. Scanning the input from right to left assigns later equal records to later positions, preserving their original relative order. A forward scan with the same decrement operation reverses equal records and is not stable.

Radix Sort

What if your integers don’t fit in a small range — but they do have a bounded number of digits? Radix sort sorts by individual digits (or fixed-width chunks of bits), from the least significant to the most significant, using a stable sort — typically counting sort, restricted to the 10 (or however many) possible digit values — as a subroutine at each pass:

Sort [170, 45, 75, 90, 802, 24, 2, 66] by ones digit:  [170, 90, 802, 2, 24, 45, 75, 66]
Then by tens digit (stable!):                          [802, 2, 24, 45, 66, 170, 75, 90]
Then by hundreds digit (stable!):                      [2, 24, 45, 66, 75, 90, 170, 802]

The correctness invariant is: after k passes, the sequence is sorted by the k processed low-order digits, interpreted together as one key. The next pass sorts by digit k. It may reorder records with different new digits, as required, while stability preserves the established low-digit order among records whose new digit is equal. Induction therefore establishes the invariant after every pass. After the most-significant digit is processed, the composite key is the complete number, so the sequence is sorted.

An unstable per-digit sort can reverse the low-digit order inside a group that ties on the new digit, destroying the invariant. For example, after the ones pass places 21 before 22, an unstable tens pass is permitted to reverse those two equal-tens records and produce 22,21.

Radix sort runs in Θ(d · (n + k)), where d is the number of digits and k is the base (e.g. 10 for decimal digits, or 256 for byte-wise passes on binary data). When d is small and fixed — sorting fixed-width integers, IP addresses, or fixed-length strings — this is effectively Θ(n), again entirely outside the reach of the comparison-sort lower bound, for exactly the same fundamental reason counting sort was: it never asks “which is bigger,” only “which bucket does this belong in.”

External Sorting

When the data does not fit in main memory, comparison count is no longer the dominant resource; transfers between storage and memory are. External merge sort is designed around long sequential I/O:

1. Read a memory-sized block.
2. Sort the block in memory and write it as a sorted run.
3. Repeat until the input becomes a sequence of sorted runs.
4. Merge many runs at once using one input buffer per run and a min-priority queue for their current front records.
5. Repeat merge passes until one run remains.

If memory holds M records and a transfer block holds B, initial run generation creates about n/M runs. A k-way merge reduces the number of passes compared with pairwise merging; k is limited by buffers and file handles. Every pass reads and writes the full data, so minimizing passes usually matters far more than saving a few comparisons.

External sorting favors merge sort because merging reads and writes sequentially. Quicksort’s scattered partitions can cause expensive random storage access. Replacement selection keeps a heap of in-memory records and defers records that would break the current run, often producing initial runs longer than memory. Compression reduces transferred bytes when decompression is cheaper than storage I/O. Asynchronous prefetching overlaps computation with the next block read, while striping runs across devices permits parallel reads and writes. Each technique targets transfers or latency rather than changing comparison order alone.

Failure handling is part of the algorithmic contract: temporary-run space, interrupted writes, stable record comparison, and cleanup must be planned before processing a dataset larger than memory.

Quickselect

Sorting is unnecessary when only the element of rank k is needed. Quickselect uses quicksort’s partitioning but recurses into only the side containing the desired rank.

#include <stdbool.h>
#include <stddef.h>

static void swap_int(int *a, int *b) {
    int temporary = *a;
    *a = *b;
    *b = temporary;
}

static size_t partition_range(int a[], size_t lo, size_t hi) {
    int pivot = a[hi];
    size_t boundary = lo;
    for (size_t i = lo; i < hi; ++i) {
        if (a[i] < pivot) {
            swap_int(&a[i], &a[boundary]);
            ++boundary;
        }
    }
    swap_int(&a[boundary], &a[hi]);
    return boundary;
}

/* Returns false when n==0 or k is outside [0,n). Mutates a. */
bool quickselect(int a[], size_t n, size_t k, int *result) {
    if (a == NULL || result == NULL || n == 0U || k >= n) {
        return false;
    }

    size_t lo = 0;
    size_t hi = n - 1U;
    while (lo <= hi) {
        size_t pivot = partition_range(a, lo, hi);
        if (pivot == k) {
            *result = a[pivot];
            return true;
        }
        if (pivot < k) {
            lo = pivot + 1U;
        } else {
            if (pivot == 0U) {
                break;
            }
            hi = pivot - 1U;
        }
    }
    return false;
}

Partitioning establishes that every item left of the pivot is smaller and the pivot occupies its final rank under the chosen duplicate policy. If that rank is k, the answer is final; otherwise only one side can contain rank k. This proves discarding the other side is safe.

If every pivot leaves at most a fixed fraction of the current range on the selected side, the scanned sizes form a geometric series and total time is Theta(n). Selecting pivot ranks independently and uniformly gives Theta(n) expected time. The shown implementation always chooses the last item and therefore has no input-independent expected guarantee; consistently extreme pivots produce Theta(n^2) time. Randomly selecting the pivot before each call to partition_range, or uniformly shuffling once before selection, supplies the expected bound. Median-of-medians pivot selection guarantees linear worst-case time with larger constants. The iterative implementation uses O(1) auxiliary space, mutates the array, and does not sort the other items.

Choosing a Sort

The following constraints narrow the strategy:

1. Key structure. A small integer range supports counting sort; a bounded number of fixed-radix digits supports radix sort. Arbitrary comparable keys require a comparison sort.
2. Stability. Stable merge sort or insertion sort preserves the order of equal records. Plain quicksort and heapsort do not.
3. Memory. Merge sort’s auxiliary array costs Theta(n) space. Heapsort uses constant auxiliary element storage, while quicksort also needs its recursion stack.
4. Adversarial input. Deterministic quicksort with a predictable pivot can be forced into quadratic time. Randomization, three-way partitioning, or a worst-case-safe fallback reduces this risk.
5. Existing order and size. Insertion sort is effective for small or nearly sorted ranges. Hybrid sorts use it for small partitions or runs, while a scalable method handles the rest.
6. Storage medium. Data larger than memory favors external merge sorting and sequential I/O.

Sorting Review

• Sorting strategies differ in stability, adaptivity, mutation, auxiliary space, guarantees, and key assumptions.
• Bubble, selection, and insertion sort are quadratic in the worst case but have distinct practical properties.
• Merge sort guarantees Theta(n log n) with linear auxiliary storage; quicksort is typically fast but needs pivot defenses; heapsort gives an in-place worst-case guarantee.
• Every comparison sort requires Omega(n log n) comparisons in the worst case.
• Counting and radix sort evade that lower bound by exploiting bounded key structure, with stability essential to radix composition.
• External merge sorting minimizes storage passes when data exceeds memory.
• Randomized Quickselect obtains one order statistic in expected linear time without fully sorting; a deterministic extreme pivot can make it quadratic.
• Real selection depends on data distribution, size, memory, stability, adversarial exposure, and output needs.

Sorting Problems

Elementary Counts

1. Count exact key comparisons and record movements made by bubble, selection, and insertion sort on sorted, reverse-sorted, and all-equal arrays of length eight. Keep comparison and movement totals separate.
2. List every inversion in [4,1,3,2]. Trace insertion sort and verify that its shifts remove exactly those inversions.
3. Give a smallest tagged-record example showing that selection sort is unstable. Explain why changing only its comparison from < to <= does not restore stability.
4. Derive the best and worst number of comparisons for optimized bubble sort. State which input family attains each bound.

Partition Traces

5. Trace Lomuto, Hoare, and three-way partitioning on [4a,2,4b,1,4c,3]. Record each scheme’s returned boundary or equal region and the recursive ranges it requires.
6. Construct a 16-element input that forces last-pivot quicksort into quadratic time. Draw the subproblem sizes and sum the partition work.
7. Find an input on which median-of-three chooses a poor pivot repeatedly. Explain why deterministic sampling reduces common failures without providing a probabilistic guarantee.
8. Prove that recursing on the smaller partition and iterating over the larger limits quicksort’s call-stack depth to O(log n), even when partition work is quadratic.

Ordering Proofs

9. State and prove the merge-loop invariant, including orderedness, permutation preservation, and stability on equal tagged records.
10. Prove insertion sort correct from its sorted-prefix invariant. Then identify the exact line whose comparison controls stability.
11. Complete the decision-tree lower bound by proving log_2(n!) = Theta(n log n) without relying on the full Stirling formula.
12. Prove the radix invariant after k least-significant-digit passes. Construct a two-pass example where an unstable digit sort produces the wrong final order.
13. Derive bottom-up heap construction’s Theta(n) bound by grouping nodes by height. Contrast it with inserting all keys one at a time.

Sorting Implementations

14. Rewrite merge sort to allocate one n-element scratch buffer at the top level and reuse it for every merge. Compare allocation count, peak space, and failure behavior with the chapter version.
15. Implement stable counting sort for records whose integer key lies in [minimum,maximum], including checked range arithmetic when minimum may be negative.
16. Implement byte-wise radix sort for unsigned 32-bit integers. State endianness-independent digit extraction and prove four stable passes suffice.
17. Build an introsort: randomized or median-sampled quicksort, insertion sort below a small cutoff, and heapsort after a depth limit. Justify each transition and test duplicate-heavy adversarial arrays.

Workload Decisions

18. Choose and justify algorithms for ten million stable score records with keys 0..100; a few hundred adversarial strings; a nearly sorted event log; and a dataset three times larger than RAM. Include memory, stability, and failure requirements.
19. Given memory for M records and block size B, estimate initial run count, feasible merge fan-in, number of merge passes, and total records transferred for an external sort of n records.
20. Compare sorting once plus binary search against repeated linear scans for q queries. Derive a symbolic crossover condition and then discuss how preserving original order changes space.

Selection Problems

21. Trace quickselect for the fourth-smallest item in [9,1,8,2,7,3,6,4,5]. List only the ranges that remain live after each partition.
22. Modify Quickselect to use three-way partitioning and return the entire rank interval occupied by keys equal to the selected value.
23. Design a streaming algorithm that maintains the smallest k of n items without sorting all input. Compare a size-k heap with Quickselect when data is all available in memory.
24. Derive the median-of-medians recurrence T(n) <= T(n/5) + T(7n/10+O(1)) + O(n) and prove it is linear. Identify why groups of five create the needed discard fraction.