Beyond comparison sorting

ACompressed recap

🧾

Comparison sorts need ⌈log n!⌉ = Ω(n log n) comparisons (3, 5, 7, 10 for n = 3, 4, 5, 6); merge and heapsort are optimal. Table: insertion for nearly sorted; heapsort O(1) space; merge stable; quick fastest on average. Counting sort Θ(n + k), stable; LSD radix Θ(d(n + b)) with stable passes; bucket sort average Θ(n) for uniform keys. Selection: min n − 1; min & max 3n/2 − 2 (even) / 3⌊n/2⌋ (odd); second largest n + ⌈log n⌉ − 2; quickselect average Θ(n); median of medians worst Θ(n); k smallest via heap Θ(n + k log n).

BMerged rule card

3.3.1 The Ω(n log n) lower bound for comparison sorting; comparing all sorts

• Comparison sorting needs ≥ ⌈log n!⌉ = Ω(n log n) comparisons (worst and average).
• Merge sort and heapsort are optimal; quicksort optimal on average.
• Table: insertion for nearly sorted; heapsort for O(1) space; merge for stable; quicksort fastest on average.

3.3.2 Counting sort, radix sort and bucket sort

• Counting sort: counts, prefix sums, place right-to-left; Θ(n + k); stable; needs k = O(n).
• LSD radix: stable digit sorts, least significant first; Θ(d(n + b)).
• Bucket sort: uniform keys, average Θ(n), worst Θ(n²).
• Non-comparison sorts escape the n log n bound.

3.3.3 Selection: minimum and maximum, second largest, k-th smallest

• Min (or max): n − 1. Min and max: 3n/2 − 2 (n even), 3⌊n/2⌋ (n odd).
• Second largest: n + ⌈log n⌉ − 2 (tournament).
• Quickselect: average Θ(n), worst Θ(n²). Median of medians: worst Θ(n).
• k smallest with a heap: Θ(n + k log n).

CInterleaved GATE-style questions

Q1NAT1 markLower bound

Minimum worst-case comparisons to sort 7 elements by comparisons?

Numerical answer: ________

Q2MCQ1 markLinear sort

n integers in the range 0 … n² − 1 are sorted by radix sort with base n. Time?

• (A) Θ(n² log n)
• (B) Θ(n)
• (C) Θ(n log n)
• (D) Θ(n²)

Q3NAT2 marksCounting

Counting sort on [3, 0, 3, 1, 2, 0, 3] with keys 0 … 3. Prefix-sum value C[2]?

Numerical answer: ________

Q4NAT1 markMin-max

Comparisons for min and max of 1,000 elements (pairing)?

Numerical answer: ________

Q5NAT2 marksSecond largest

Minimum comparisons for the second largest of 32 elements?

Numerical answer: ________

Q6MCQ1 markStable digits

LSD radix sort requires each digit pass to be:

• (A) in-place
• (B) stable
• (C) recursive
• (D) comparison-based

Q7MSQ2 marksSelection facts

Which are true?

• (A) Finding the k smallest elements in sorted order with a heap takes Θ(n log n) for every k.
• (B) Finding the minimum needs at least n − 1 comparisons.
• (C) Median of medians guarantees Θ(n) worst case.
• (D) Quickselect runs in Θ(n) on average.

Q8MCQ1 markSort choice

Which sort is best for a linked list of n records that must stay stable, in Θ(n log n) worst case?

• (A) Heapsort
• (B) Selection sort
• (C) Quicksort
• (D) Merge sort

DAnswer Vault