Merge Sort, Quick Sort & Linear-Time Selection
“Inversion counting, Hoare vs Lomuto partitions, randomized quicksort expected O(n log n), and BFPRT Median-of-Medians.”
1.Merge Sort Mechanics & Inversion Counting
§ 2.1.Merge Sort recursively divides the array into two halves, sorts each half, and merges the sorted sublists in linear time:
T(n) = 2T(n/2) + Theta(n) = Theta(n log n) in Best, Average, and Worst cases.
Inversion Counting:
An inversion is a pair (i, j) such that i < j but A[i] > A[j]. A completely reverse-sorted array of size n has n(n - 1) / 2 inversions.
During the merge step of two sorted subarrays Left[0..p] and Right[0..q], whenever an element Right[j] is smaller than Left[i], it is smaller than all remaining elements in Left (Left[i..p]). Hence, exactly (p - i + 1) inversions are contributed. This counts all inversions in O(n log n) time.
2.QuickSort Partition Analysis & Deterministic Linear Selection
§ 2.2.QuickSort selects a pivot element and partitions array A[p..r] into two subarrays such that elements in A[p..q-1] <= A[q] and elements in A[q+1..r] >= A[q].
Expected Analysis of Randomized QuickSort:
Let z_1 < z_2 < ... < z_n be sorted elements. Any two elements z_i and z_j are compared at most once, and are compared if and only if either z_i or z_j is chosen as pivot before any element in {z_{i+1}, ..., z_{j-1}}. The probability of this event is 2 / (j - i + 1). Total expected comparisons:
E[X] = sum_{i=1}^{n-1} sum_{j=i+1}^n frac{2}{j - i + 1} = sum_{i=1}^{n-1} sum_{k=2}^{n - i + 1} frac{2}{k} <= 2n sum_{k=1}^n frac{1}{k} = 2n ln n + O(n) = Theta(n log n).
Median-of-Medians (BFPRT Selection):
To guarantee O(n) worst-case selection of the k-th order statistic:
1. Divide n elements into lfloor n/5 rfloor groups of 5.
2. Find the median of each group (takes O(1) per group, total O(n)).
3. Recursively find the median of the medians, x (takes T(n/5)).
4. Partition array around x. At least 3 (1/2 n/5) = 3n/10 elements are <= x, and at least 3n/10 elements are >= x. Thus, the recursive subproblem on either side has size at most 7n/10.
5. Recurrence: T(n) <= T(n/5) + T(7n/10) + c * n. Since 1/5 + 7/10 = 9/10 < 1, T(n) = O(n).
3. Worked Problem: Partition Comparisons & Worst-Case Depth
Remember that in Hoare's partition, the pivot is not necessarily placed at its final sorted position after one partition call; it merely separates the array into <= pivot and >= pivot segments.
Problem: An array A contains n distinct elements. QuickSort is executed using the deterministic median-of-medians algorithm to select the pivot at each step. Find the recurrence for the number of comparisons C(n) and prove that C(n) = O(n log n) or O(n).
Step 1: Formulate the recurrence components:
- Finding medians of groups of 5: For each group of 5, finding median requires at most 7 comparisons. Total = 7 * (n/5) = 1.4 n comparisons.
- Recursive call to find median of medians x: C(n/5).
- Partitioning array around x: Exactly n - 1 comparisons.
- Selection recurses on at most 7n/10 elements: T(7n/10).
Step 2: Combine terms for full QuickSort (sorting, not selection):
T(n) = T(k) + T(n - k) + C_partition(n) + T_pivot_selection(n).
With BFPRT pivot selection, 3n/10 <= k <= 7n/10.
The worst-case split is 3n/10 and 7n/10.
T(n) = T(3n/10) + T(7n/10) + O(n).
Step 3: Solve via recursion tree:
At each depth, work is (3/10 + 7/10) n = n.
Maximum depth of tree: log_{10/7} n = O(log n).
Total time = Depth * Work per level = O(n log n) guaranteed worst case!
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Best visual explanations of algorithm design and complexity analysis.
Exam-focused with GATE PYQ numericals on every major algorithm.