Mechanism (Divide and Conquer, In-Place)

1. Choose a pivot element (first, last, random, or median-of-three)
2. Partition: rearrange array so elements < pivot go left, elements > pivot go right
3. Recurse on left and right partitions

Pseudocode

QUICK_SORT(arr, low, high):
  IF low < high:
    p = PARTITION(arr, low, high)
    QUICK_SORT(arr, low, p-1)
    QUICK_SORT(arr, p+1, high)

Complexity

• Best/Average: O(n log n)
• Worst: O(n²) — occurs when pivot selection is consistently poor (e.g., already-sorted array with first-element pivot) causing maximally unbalanced partitions
• Space: O(log n) average (recursion stack, in-place sort — no extra array needed)
• Not stable by default

Why It's Usually Preferred Over Merge Sort in Practice

• In-place (O(log n) space vs Merge Sort's O(n)) and has smaller constant factors — faster in practice despite same average complexity, provided pivot selection avoids worst case (randomized/median-of-three pivot mitigates this)

Exam Angle / MCQ Trap

High-frequency question: "Explain why Quick Sort's worst case is O(n²) and how to avoid it." Answer: poor/deterministic pivot choice on already-sorted or reverse-sorted data — mitigated via randomized pivot or median-of-three selection.

📌 Sample & Repeated FPSC Questions (2016–2026)

2025, Paper I, Q6(c) (8 marks) — Sort the parcel weights [30, 45, 10, 20, 75, 15, 85, 40, 5, 65] in ascending order using Quick Sort. Clearly indicate the choice of pivot and reason for it, with a graphical representation of each step.

Pivot choice: last element of each (sub)array (Lomuto partition scheme) — simple, in-place (no extra memory), and gives good average-case O(n log n) performance; it's the classic textbook scheme (production libraries usually add median-of-three on top to dodge the worst case).

Array (idx 0-9): [30, 45, 10, 20, 75, 15, 85, 40, 5, 65]

QS(0,9)  pivot=65 → partition:
  [30, 45, 10, 20, 15, 40, 5 | 65 | 85, 75]        (65 fixed at idx 7)

QS(8,9)  pivot=75 (right part [85,75]) → [75 | 85]
  → [ ... , 65, 75, 85]                             (idx 7,8,9 fixed)

QS(0,6)  pivot=5 (left part [30,45,10,20,15,40,5]) → partition:
  [5 | 45, 10, 20, 15, 40, 30]                      (5 fixed at idx 0)

QS(1,6)  pivot=30 ([45,10,20,15,40,30]) → partition:
  [10, 20, 15 | 30 | 40, 45]                        (30 fixed at idx 4)

QS(1,3)  pivot=15 ([10,20,15]) → partition:
  [10 | 15 | 20]                                    (15 fixed; 10, 20 already single)

QS(5,6)  pivot=45 ([40,45]) → already ordered → [40 | 45]

Final sorted array: [5, 10, 15, 20, 30, 40, 45, 65, 75, 85]

Key reasoning points: