Ch13 Sorting · Ahmet Çelik

Numbering note: The course labels this material Ch13 (Sorting). In the 6th-edition textbook, sorting and selection live in Chapter 12, and the heap material this deck depends on is Chapter 9. All Textbook §X.X citations below use the textbook’s own section numbers so they point to the correct pages.

0. Overview

The slides do not give a one-line formal definition of sorting; they begin directly with priority-queue–based sorting.

Note: Not explicitly covered in slides. (Textbook §12) — Formally, sorting takes a sequence of n elements drawn from a total order and produces a permutation of them in nondecreasing order according to a comparator.

The slides distinguish sorting algorithms along three axes that appear repeatedly in the summary tables (slides 41, 59): running time, whether the algorithm is in-place, and whether data is accessed sequentially. Slide 61 adds a fourth axis: whether the algorithm is comparison-based, i.e. it orders elements only by asking “is x_i < x_j?”.

Stability is a fifth axis you will be expected to know:

Note: Stability is not discussed anywhere in the uploaded slides. (Textbook §12.4) — A sort is stable if equal keys keep their original relative order.

Why O(n log n) is the comparison-based lower bound

Slides 60–64 give the decision-tree argument. Any comparison-based algorithm’s execution is a root-to-leaf path in a binary decision tree whose internal nodes are comparisons. Every one of the n! input permutations must reach a distinct leaf. A binary tree with n! leaves has height at least log(n!). Since log(n!) ≥ log((n/2)^(n/2)) = (n/2)·log(n/2), every comparison-based sort runs in Ω(n log n) time.

Selection-Sort (PQ-sort with unsorted sequence)

Strategy: Insert all elements into an unsorted-list priority queue, then repeatedly extract the minimum.

Invariant:

Phase 1 is O(n) (trivial appends); phase 2 forces each removeMin to scan the full unsorted PQ, costing 1 + 2 + … + n = O(n²).

public static <K> void selectionSort(K[] S, Comparator<K> comp) {
    int n = S.length;
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++)
            if (comp.compare(S[j], S[min]) < 0) min = j;
        K temp = S[i]; S[i] = S[min]; S[min] = temp;
    }
}

Note: Java realization is textbook/general background. (Textbook §9.4.1)

Case	Time	Space	Why
Best	O(n²)	O(1)	Even sorted input: every removeMin scans the full unsorted PQ.
Average	O(n²)	O(1)	removeMin scans dominate regardless of order.
Worst	O(n²)	O(1)	Cost proportional to 1 + 2 + … + n (slide 4).

Stable? No — swapping a distant min past equal keys. (Textbook §12.4)

In-place? Yes (slide 8). Comparison-based? Yes (slide 61).

Trace (slide 5): Input (7,4,8,2,5,3,9). Phase 2 pulls 2, 3, 4, 5, 7, 8, 9 in order.

Special: No best-case escape — Theta(n²) always. Contrast with insertion-sort: selection is cheap to fill, expensive to drain; insertion-sort is the reverse.

Insertion-Sort (PQ-sort with sorted sequence)

Strategy: Insert elements into a sorted-list PQ; extract minima trivially (already in order).

Invariant:

The PQ is kept sorted; each new element slides leftward past larger keys until it reaches its correct position.

public static <K> void insertionSort(K[] S, Comparator<K> comp) {
    for (int i = 1; i < S.length; i++) {
        K cur = S[i];
        int j = i - 1;
        while (j >= 0 && comp.compare(S[j], cur) > 0) {
            S[j + 1] = S[j]; j--;
        }
        S[j + 1] = cur;
    }
}

Case	Time	Space	Why
Best	O(n)	O(1)	Sorted input: each key compares once with its left neighbour and stops.
Average	O(n²)	O(1)	Each insertion shifts about half the sorted prefix.
Worst	O(n²)	O(1)	Reverse-sorted: each element shifts past the entire prefix.

Stable? Yes — strict “>” loop stops before equal keys. (Textbook §12.4)

Trace (slide 7): (7,4,8,2,5,3,9) → (7) → (4,7) → (4,7,8) → (2,4,7,8) → … → (2,3,4,5,7,8,9).

In-place? Yes (slide 8). Comparison-based? Yes (slide 61).

Heap Sort

Strategy: PQ-sort with a binary heap so both insert and removeMin cost O(log n).

Invariant:

Heap-order: every node’s key ≤ its children’s keys. This forces the global minimum to the root; removeMin returns the next sorted element in O(log n).

Array-based heap (slide 11): node at rank i → left child at 2i+1, right child at 2i+2. add inserts at rank n+1 and up-heaps; removeMin moves the last entry to the root and down-heaps. Yields in-place heap-sort.

static void downHeap(int[] heap, int i, int n) {
    while (2 * i + 1 < n) {
        int child = 2 * i + 1;
        int right = 2 * i + 2;
        if (right < n && heap[right] < heap[child]) child = right;
        if (heap[i] <= heap[child]) break;
        int t = heap[i]; heap[i] = heap[child]; heap[child] = t;
        i = child;
    }
}

Note: Textbook/general background. (Textbook §9.3)

Case	Time	Space	Why
Best	O(n log n)	O(1)	Each removeMin may down-heap along a full root-to-leaf path of length ⌊log₂ n⌋.
Average	O(n log n)	O(1)	Bound holds independent of input order.
Worst	O(n log n)	O(1)	n operations each O(log n); no input defeats the height bound.

Stable? No. In-place? Yes (slide 11). Comparison-based? Yes (slide 61).

Bottom-up heap construction (slides 14–19): Merge pairs of heaps bottom-up in log n phases. Each node lies on at most two proxy paths → total cost O(n) (slide 19).

Exam trap: Bottom-up build is O(n), but phase 2 (n × removeMin) is still O(n log n). Heap-sort is O(n log n) total.

1. Merge Sort

Strategy: Divide-and-conquer (slide 21): split in half, recursively sort each half, merge.

Invariant:

Both halves are sorted before merge; merge picks the smaller front element each step, so every comparison emits one element in final position → O(n) merge cost.

Pseudocode (slide 22):

Algorithm mergeSort(S)
    if S.size() > 1
        (S1, S2) <- partition(S, n/2)
        mergeSort(S1)
        mergeSort(S2)
        S <- merge(S1, S2)

Exact slide Java (slides 24–25):

public static <K> void merge(K[] S1, K[] S2, K[] S, Comparator<K> comp) {
    int i = 0, j = 0;
    while (i + j < S.length) {
        if (j == S2.length || (i < S1.length && comp.compare(S1[i], S2[j]) < 0))
            S[i + j] = S1[i++];  // copy ith element of S1 and increment i
        else
            S[i + j] = S2[j++];  // copy jth element of S2 and increment j
    }
}

public static <K> void mergeSort(K[] S, Comparator<K> comp) {
    int n = S.length;
    if (n < 2) return;              // array is trivially sorted
    int mid = n / 2;
    K[] S1 = Arrays.copyOfRange(S, 0, mid);   // copy of first half
    K[] S2 = Arrays.copyOfRange(S, mid, n);   // copy of second half
    mergeSort(S1, comp);            // sort copy of first half
    mergeSort(S2, comp);            // sort copy of second half
    merge(S1, S2, S, comp);         // merge sorted halves back into original
}

Case	Time	Space	Why
Best	O(n log n)	O(n)	Height O(log n), O(n) work per level (tree shape is input-independent).
Average	O(n log n)	O(n)	Same: 2^i subproblems of size n/2^i at depth i, each level totals O(n).
Worst	O(n log n)	O(n)	Balanced split is forced regardless of input.

Stable? Yes — strict “<” takes from S1 first when equal. (Textbook §12.4)

In-place? No — uses auxiliary arrays S1, S2. Comparison-based? Yes (slide 61).

Trace (slides 27–36): 7 2 9 4 | 3 8 6 1 → singletons → 2 7, 4 9, 3 8, 1 6 → 2 4 7 9, 1 3 6 8 → 1 2 3 4 6 7 8 9.

Recurrence (slide 38): T(n) = b if n < 2; T(n) = 2T(n/2) + bn if n ≥ 2. Closed form (slides 39–40): T(n) = bn + bn·log n = O(n log n).

Contrast vs Quick Sort: Both D&C, O(n log n) average. Merge: cheap divide, expensive merge, O(n log n) worst, stable, O(n) space. Quick: expensive partition, trivial join, O(n²) worst, unstable, O(1) space (in-place). Prefer merge for guaranteed performance or stability; prefer quick for in-memory speed.

2. Quick Sort

Strategy: Randomized D&C (slide 43): pick random pivot x, partition into L (<x), E (=x), G (>x); sort L and G; join.

Invariant:

After partition, every element of L < x, every element of G > x — E is already final. No merge needed; concatenation suffices.

Partition pseudocode (slide 44):

Algorithm partition(S, p)
    L, E, G <- empty sequences
    x <- S.remove(p)
    while not S.isEmpty()
        y <- S.remove(S.first())
        if y < x         L.addLast(y)
        else if y = x    E.addLast(y)
        else             G.addLast(y)
    return L, E, G

In-place partition (slides 56–58): Two indices j (scan right for element > x) and k (scan left for element < x), swap, repeat until they cross. Random pivot: i <- random integer between l and r (slide 56).

// Textbook-style in-place; slide uses random pivot (Textbook §12.2.2)
public static <K> void quickSort(K[] S, Comparator<K> comp, int a, int b) {
    if (a >= b) return;
    K pivot = S[b];
    int left = a, right = b - 1;
    while (left <= right) {
        while (left <= right && comp.compare(S[left], pivot) < 0)  left++;
        while (left <= right && comp.compare(S[right], pivot) > 0) right--;
        if (left <= right) {
            K t = S[left]; S[left] = S[right]; S[right] = t;
            left++; right--;
        }
    }
    K t = S[left]; S[left] = S[b]; S[b] = t;
    quickSort(S, comp, a, left - 1);
    quickSort(S, comp, left + 1, b);
}

Case	Time	Space	Why
Best	O(n log n)	O(log n)	Near-median pivot → balanced halves → O(log n) depth.
Expected	O(n log n)	O(log n)	Good call (both halves < 3s/4) has prob 1/2 → expected height O(log n), O(n)/level (slides 54–55).
Worst	O(n²)	O(n)	Unique min/max pivot always → partitions n-1 and 0 → T(n)=T(n-1)+O(n) (slide 53).

Stable? No. In-place? Yes (slides 56–58). Comparison-based? Yes (slide 61).

Trace (slides 46–52): Input 7 2 9 4 3 7 6 1 → partition, recurse L/G, join → 1 2 3 4 6 7 7 9.

Selection Problem and Quick-Select

Problem (slide 66): Given k and n elements, find the k-th smallest. Sort + index is O(n log n); quick-select is faster.

Quick-Select (slide 67): Randomized prune-and-search. Partition into L, E, G: if k ≤ |L| recurse in L; if k ≤ |L|+|E| return pivot x; else recurse in G for rank k−|L|−|E|.

Case	Time	Why
Expected	O(n)	Recurse one side only: T(n) < T(3n/4) + 2bn, geometric series sums to O(n) (slide 71).
Worst	O(n²)	Extreme pivots shrink problem by 1 each time.

Deterministic O(n) (slide 72): Median-of-medians — split into groups of 5, find each median, recursively select median-of-medians as pivot → worst-case O(n).

4. Bucket / Radix / Counting Sort

Note: None appear in the uploaded slides. (Textbook §12.3.2)

These beat Ω(n log n) only because they are not comparison-based — they exploit integer/key structure, achieving O(n+N) or O(d(n+N)) for bounded-range keys.

5. Comparison Lower Bound

Every comparison-based sort’s execution is a root-to-leaf path in a binary decision tree (slide 62). Height = lower bound on worst-case time. n! leaves required (one per permutation, slide 63). Height ≥ log(n!) ≥ (n/2)·log(n/2) = Ω(n log n) (slide 64).

Any comparison-based sorting algorithm runs in Ω(n log n) time. Merge-sort, heap-sort, and (expected) quick-sort are asymptotically optimal.

6. Algorithm Comparison Table

Algorithm	Best	Average	Worst	Space	Stable¹	In-place	Notes
Selection-sort	O(n²)	O(n²)	O(n²)	O(1)	No	Yes	Small data (<1K) (slide 41)
Insertion-sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Small/nearly-sorted (slide 41)
Heap-sort	O(n log n)	O(n log n)	O(n log n)	O(1)	No	Yes	Large data (1K–1M) (slide 41)
Merge-sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No	Huge data (>1M); sequential (slide 41)
Quick-sort	O(n log n)	O(n log n) exp.	O(n²)	O(log n)	No	Yes	Fastest in practice; randomized (slide 59)

¹ Stability from Textbook §12.4; slides are silent on stability.

7. Common Exam Traps

“Merge-sort is in-place.” False — O(n) extra space (slides 41, 59).
“Quick-sort is O(n log n) worst case.” False — O(n²) worst; O(n log n) is expected (slide 53).
“Bottom-up heap build makes heap-sort O(n).” False — build is O(n), but n removeMin operations cost O(n log n) (slide 19).
“A clever comparison sort can beat n log n.” False — decision-tree lower bound is Ω(n log n) (slide 64).
“Selection-sort has a fast best case.” False — Theta(n²) always; insertion-sort has the O(n) best case.
Heap child indices: left = 2i+1, right = 2i+2 (0-indexed, slide 11). Don’t confuse with 1-based 2i/2i+1.
Stability claims must be mechanistically justified (e.g. merge uses strict “<”).

8. Quick-Reference Summary

Use insertion-sort for tiny or nearly-sorted inputs. Use heap-sort for guaranteed O(n log n) in-place. Use merge-sort for guaranteed O(n log n) with stability or sequential/disk access. Use quick-sort as the default in-memory sort. Use quick-select when only the k-th smallest is needed (expected O(n)). No comparison-based method beats Ω(n log n) (slide 64).

Quick-Reference Complexity Summary

Algorithm	Best	Average	Worst	Space	Notes
Selection-Sort	O(n²)	O(n²)	O(n²)	O(1)	in-place, not stable
Insertion-Sort	O(n)	O(n²)	O(n²)	O(1)	in-place, stable, O(n) best
Heap-Sort	O(n log n)	O(n log n)	O(n log n)	O(1)	in-place, not stable
Merge-Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	stable, not in-place
Quick-Sort	O(n log n)	O(n log n) exp.	O(n²)	O(log n)	in-place, not stable
Quick-Select	O(n)	O(n) exp.	O(n²)	O(log n)	selection only
Bottom-up heap build	O(n)	O(n)	O(n)	O(1)	phase-1 speedup (slide 19)