2.3Quick sort
The idea
Quick sort picks a pivot, puts smaller items before it and larger after, and recurses on both sides.
Think of it like this: Sorting a class by picking one student as reference: shorter ones to the left, taller to the right.
Why it exists
GATE asks the array after one partition and the worst-case recurrence.
How it works
- Choose the pivot (here the last element).
- Scan: move items ≤ pivot to the left part.
- Put the pivot between the two parts: it is now final.
- Recurse on each part. Worst case: always a 1 : n − 1 split.
Worked example: Already sorted input, last-element pivot
Each partition removes just one element: T(n) = T(n − 1) + n = Θ(n²). A balanced split gives 2T(n/2) + n = Θ(n log n).
Now play with it
- →Run the default array and watch the pivot (yellow) find its final index (green).
- →Switch the input to 1 2 3 4 5 6 7 8 and count the comparisons.
- Start: 8 3 7 1 5 9 2 6
- pivot = 6 (last element), partition [0..7]
- 8 > 6: leave on the big side
- 3 ≤ 6: swap into the small side
- 7 > 6: leave on the big side
- 1 ≤ 6: swap into the small side
- 5 ≤ 6: swap into the small side
- 9 > 6: leave on the big side
- 2 ≤ 6: swap into the small side
- place pivot 6 at its final index 4
- pivot = 2 (last element), partition [0..3]
- 3 > 2: leave on the big side
- 1 ≤ 2: swap into the small side
- 5 > 2: leave on the big side
- place pivot 2 at its final index 1
- pivot = 3 (last element), partition [2..3]
- 5 > 3: leave on the big side
- place pivot 3 at its final index 2
- pivot = 7 (last element), partition [5..7]
- 9 > 7: leave on the big side
- 8 > 7: leave on the big side
- place pivot 7 at its final index 5
- pivot = 9 (last element), partition [6..7]
- 8 ≤ 9: already in place
- place pivot 9 at its final index 7
Θ(n log n) on average, Θ(n²) when the pivot is always the smallest or largest (sorted input with this pivot rule). Not stable.
Check yourself
Quick sort with the last element as pivot on an already sorted array takes
Exam notes (the dense version)
Choose a pivot, partition into smaller and larger, recurse. Average and best Θ(n log n); worst Θ(n²) when the pivot is always an extreme (already sorted input with a first or last pivot, or all-equal keys with a naive partition). T(n) = T(n − 1) + n. Not stable, in place (O(log n) stack on average). A median pivot gives T(n) = 2T(n/2) + n.
Previous year questions: Sorting & Searching (9)
PYQs are grouped by topic, so this is the full set for Sorting & Searching; try the ones that match this subtopic. Open all 9 on the topic page.