Sorting I

Why Sorting? The Set Interface Connection

In Chapter 2 we built Sequence data structures — arrays, linked lists, dynamic arrays. They all store items in an order you impose. But a different interface matters more for search: the Set interface, where items have intrinsic keys and you query by key value rather than position.

So sorting is not an end in itself — it is the prerequisite for efficient Set operations. Every chapter from here through Chapter 8 is about building faster and faster Set implementations, all starting from the ability to sort.

The Sorting Problem — Precisely Stated

Before analysing good algorithms, let us see the worst possible one — just to appreciate the gap.

Permutation sort: there are $n!$ permutations of $A$; at least one is sorted. Try all of them. Correct by exhaustive case analysis. Runtime: $\Omega(n! \cdot n)$ — checking each permutation takes $\Theta(n)$. For $n = 20$, $20! \approx 2.4 \times 10^{18}$. This is not slow — it is cosmically unusable.

Algorithm 1 — Selection Sort

The first sensible idea: at each step, find the largest unsorted element and put it in its final position. After $i$ steps, the $i$ largest elements are correctly placed at the end of the array.

Invariant: after iteration $i$, sub-array $A[n-i:]$ contains the $i$ largest elements in sorted order, and $A[:n-i]$ contains the remaining elements in some order.

def selection_sort(A):
    """Sort array A in-place. Θ(n²) comparisons, O(n) swaps."""
    n = len(A)
    for i in range(n - 1, 0, -1):      # i goes n-1, n-2, ..., 1
        m = i                           # assume A[i] is max of A[:i+1]
        for j in range(i):              # scan A[:i] for a larger element
            if A[j] > A[m]:
                m = j                   # found new max
        A[m], A[i] = A[i], A[m]        # swap max into final position


# Example: sort NIFTY weekly expiry strikes
strikes = [24500, 24000, 23500, 25000, 23000]
selection_sort(strikes)
print(strikes)  # [23000, 23500, 24000, 24500, 25000]

#include <vector>
#include <algorithm>
using namespace std;

// Selection sort — Θ(n²) comparisons, O(n) swaps, in-place
void selection_sort(vector<int>& A) {
    int n = A.size();
    for (int i = n - 1; i > 0; --i) {
        int m = i;                      // index of current max
        for (int j = 0; j < i; ++j)
            if (A[j] > A[m]) m = j;    // find max in A[0..i]
        swap(A[m], A[i]);               // place max at A[i]
    }
}

// Example
// vector<int> strikes = {24500, 24000, 23500, 25000, 23000};
// selection_sort(strikes);
// → {23000, 23500, 24000, 24500, 25000}

Complexity analysis via recurrence. Let $T(n)$ be the time to sort $n$ elements. Finding the max in a prefix of length $i$ takes $\Theta(i)$. The recurrence is:

Selection sort is in-place ($O(1)$ extra space) and uses at most $O(n)$ swaps — the minimum possible for a comparison sort. But it is not stable: swapping can move equal elements out of their original relative order.

Algorithm 2 — Insertion Sort

Different invariant: at each step, the first $i$ elements are sorted among themselves. Insert the next element into its correct position in the sorted prefix by sliding it left until it finds its place.

Invariant: after iteration $i$, sub-array $A[:i]$ is sorted. The remaining elements are untouched.

def insertion_sort(A):
    """Sort array A in-place. Stable. Θ(n²) worst case, Θ(n) if nearly sorted."""
    for i in range(1, len(A)):
        j = i
        # slide A[j] left until it finds its sorted position
        while j > 0 and A[j] < A[j - 1]:
            A[j - 1], A[j] = A[j], A[j - 1]
            j -= 1


# Key insight: insertion sort is fast on nearly-sorted data.
# If A is already sorted, the while loop never executes — Θ(n) total.
# Real-world use: TimSort (Python's built-in sort) uses insertion sort
# for small subarrays (n < 64) because cache locality dominates there.

#include <vector>
using namespace std;

// Insertion sort — stable, in-place, Θ(n²) worst, Θ(n) if nearly sorted
void insertion_sort(vector<int>& A) {
    int n = A.size();
    for (int i = 1; i < n; ++i) {
        int key = A[i];
        int j   = i - 1;
        // shift elements greater than key one position right
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            --j;
        }
        A[j + 1] = key;     // insert key in its correct position
    }
}
// Note: C++ version uses shifts (not swaps) — same O complexity,
// but ~2x fewer memory writes in practice on sorted-ish data.

Algorithm 3 — Merge Sort

Both $\Theta(n^2)$ algorithms share the same structure: fix one element per pass, paying $\Theta(n)$ per pass, for $n$ passes total. To do better, we need to fix more structure per pass. Merge sort achieves this by divide and conquer.

Idea: recursively sort the left and right halves, then merge the two sorted halves into one sorted array. The merge step scans both halves simultaneously — two pointers walking from back to front — and takes $\Theta(n)$.

def merge_sort(A, a=0, b=None):
    """Sort A[a:b] in-place. Θ(n log n) time, Θ(n) extra space."""
    if b is None: b = len(A)
    if b - a <= 1: return           # base case: 0 or 1 element

    c = (a + b + 1) // 2           # midpoint (ceiling)
    merge_sort(A, a, c)             # sort left half  T(n/2)
    merge_sort(A, c, b)             # sort right half T(n/2)

    # merge: copy both halves, then merge back into A[a:b]
    L, R = A[a:c], A[c:b]          # O(n) copy
    i = j = 0
    for k in range(a, b):          # O(n) merge
        if j >= len(R) or (i < len(L) and L[i] <= R[j]):
            A[k] = L[i]; i += 1
        else:
            A[k] = R[j]; j += 1
    # Note: L[i] <= R[j] (not <) makes the sort stable

#include <vector>
using namespace std;

void merge(vector<int>& A, int a, int c, int b) {
    vector<int> L(A.begin()+a, A.begin()+c);   // copy left half
    vector<int> R(A.begin()+c, A.begin()+b);   // copy right half
    int i = 0, j = 0;
    for (int k = a; k < b; ++k) {
        if (j >= (int)R.size() || (i < (int)L.size() && L[i] <= R[j]))
            A[k] = L[i++];
        else
            A[k] = R[j++];
    }
}

void merge_sort(vector<int>& A, int a, int b) {
    if (b - a <= 1) return;         // base case
    int c = (a + b + 1) / 2;
    merge_sort(A, a, c);             // T(n/2)
    merge_sort(A, c, b);             // T(n/2)
    merge(A, a, c, b);               // Θ(n)
}

// Entry point
void merge_sort(vector<int>& A) {
    merge_sort(A, 0, A.size());
}

Solving the Merge Sort Recurrence

The recurrence is $T(1) = \Theta(1)$, $T(n) = 2T(n/2) + \Theta(n)$. We solve it two ways.

Method 1 — Substitution. Guess $T(n) = \Theta(n \log n)$. Substitute $T(n) = cn \log n$:

Method 2 — Recurrence Tree. Draw the recursion tree. At depth $i$, there are $2^i$ subproblems each of size $n/2^i$. Work at depth $i$: $2^i \cdot \Theta(n/2^i) = \Theta(n)$. The tree has depth $\log_2 n$ (base case at $n/2^i = 1$). Total:

The Master Theorem — Solving Recurrences in General

Many divide-and-conquer algorithms have recurrences of the form $T(n) = aT(n/b) + f(n)$. The Master Theorem gives the answer by comparing $f(n)$ to $n^{\log_b a}$ — the number of leaves in the recursion tree.

For merge sort: $a = 2$, $b = 2$, $f(n) = \Theta(n) = \Theta(n^1)$. So $c = 1$ and $\log_b a = \log_2 2 = 1$. Case 2 applies: $T(n) = \Theta(n^1 \log n) = \Theta(n \log n)$. ✓

Comparison — All Three Algorithms

* Merge sort is stable only if the merge step uses $\leq$ (not $<$) when choosing from the left half.