Divide-and-conquer sorts

ACompressed recap

🧾

Merge sort: merge p + q in ≤ p + q − 1 comparisons (≥ min(p, q)); Θ(n log n) always; worst comparisons n log n − n + 1 for n = 2ᵏ; stable, Θ(n) space. Quicksort: Lomuto partition (pivot last, n − 1 comparisons, pivot in final place); best/average Θ(n log n), worst Θ(n²) on sorted/reverse/equal inputs with an end pivot; constant splits stay n log n; in-place, not stable. Heapsort: bottom-up build Θ(n), n − 1 extract-and-sift steps; Θ(n log n) always; in-place, not stable.

BMerged rule card

3.2.1 Merge sort: merging, recurrence, comparison counts

• Merge p + q: ≤ p + q − 1 comparisons, ≥ min(p, q).
• Merge sort: Θ(n log n) all cases; Θ(n) extra space; stable; depth ⌈log n⌉.
• Worst comparisons W(n) = W(⌈n/2⌉) + W(⌊n/2⌋) + n − 1; n = 2ᵏ → n log n − n + 1.
• Bottom-up: ⌈log n⌉ passes.

3.2.2 Quicksort: partitioning, best, worst and average cases

• Lomuto: pivot = last; n − 1 comparisons; pivot ends in its final place.
• Best/average Θ(n log n); worst Θ(n²) (sorted or reverse with end pivot; all-equal with Lomuto).
• Constant-fraction splits → Θ(n log n). Median pivot (Θ(n)) → worst Θ(n log n).
• In-place, not stable; stack O(log n) best, O(n) worst.

3.2.3 Heapsort: build-heap in O(n), heapify, extract-max

• Sift down: swap with the larger child until in place.
• Build-heap bottom-up from ⌊n/2⌋ to 1: Θ(n). Repeated insertion: O(n log n).
• Heapsort: build, then n − 1 × (swap root with last, sift down): Θ(n log n) all cases; in-place; not stable.
• Max-heap check: A[⌊i/2⌋] ≥ A[i].

CInterleaved GATE-style questions

Q1NAT1 markMerge

Maximum comparisons to merge sorted lists of 7 and 9 elements?

Numerical answer: ________

Q2NAT2 marksMerge sort trace

Merge sort (left half = first ⌊n/2⌋) on [5, 2, 9, 1, 7, 3]. Comparisons in the final merge?

Numerical answer: ________

Q3NAT2 marksQuicksort

Quicksort (Lomuto, pivot last) on the reverse-sorted array [6, 5, 4, 3, 2, 1]. Total comparisons?

Numerical answer: ________

Q4MCQ1 markWorst-case input

Quicksort with the first element as pivot performs worst on:

• (A) any array of distinct elements
• (B) an array whose first element is the median
• (C) an already sorted array
• (D) a random array

Q5NAT2 marksPartition

Lomuto partition (pivot last) of [7, 2, 8, 1, 6, 3, 5, 4]. Final index (0-based) of the pivot?

Numerical answer: ________

Q6NAT1 markBuild-heap

Build-heap on [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]. Root value?

Numerical answer: ________

Q7MCQ1 markComplexities

Which sort is Θ(n log n) in the worst case and in-place?

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

Q8MSQ2 marksStability

Which are stable?

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

DAnswer Vault