Quicksort is a divide-and-conquer sorting algorithm that selects a pivot element, partitions the list into values smaller and larger than the pivot, and then recursively sorts each partition. It achieves an average time complexity of O(n log n), making it one of the fastest general-purpose sorting algorithms used in practice.
What is the divide-and-conquer idea behind quicksort?
Divide and conquer means breaking a big problem into smaller versions of the same problem, solving each, and combining the results. Quicksort applies this to sorting:
- Divide — choose a pivot element and partition the list so that all items less than the pivot are to its left, and all items greater are to its right.
- Conquer — recursively apply the same process to the left sub-list and the right sub-list.
- Combine — nothing to do. Once every sub-list has one element (already sorted), the whole list is sorted in place.
Think of it like sorting a class photograph by height. Pick one person as the reference (the pivot). Everyone shorter stands to their left; everyone taller stands to their right. Repeat within each group — eventually every person is in the right place.
How is a pivot chosen?
The pivot is simply one element selected from the list. The choice of pivot affects performance:
| Pivot strategy | Typical choice | Risk |
|---|---|---|
| First element | list[0] |
O(n²) on already-sorted lists |
| Last element | list[n-1] |
Same worst-case risk |
| Middle element | list[n//2] |
Safer for many real datasets |
| Median of three | Median of first, middle, last | Robust; used in real implementations |
| Random element | Random index | Probabilistically avoids worst case |
For GCSE examinations, the pivot is often specified as the first or middle element. Always state which you are using when you trace.
How does a partitioning step work? A step-by-step trace
List to sort: [7, 2, 9, 4, 1, 6, 3] — pivot chosen as first element: 7.
Goal: rearrange so all elements < 7 are left of 7, all elements > 7 are right.
| Pass | Left pointer | Right pointer | Action |
|---|---|---|---|
| Start | 2 (index 1) |
3 (index 6) |
Compare 2 < 7 and 3 < 7 |
| Step 1 | Move left right to 9 | 3 stays | 9 > 7 → left stops |
| Step 2 | 9 stays | Move right left to 6 | 6 < 7 → right stops |
| Swap | Swap 9 and 6 | [7, 2, 6, 4, 1, 9, 3] |
|
| Continue | Move to 4, then 1 | Move to 3 | Pointers cross — done |
| Place pivot | Swap 7 with element at right pointer (3) | [3, 2, 6, 4, 1, 7, 9] |
After one partition: [3, 2, 6, 4, 1] | 7 | [9]
7 is now in its final sorted position. Apply quicksort recursively to [3, 2, 6, 4, 1] and [9].
What is quicksort's time complexity?
| Case | Complexity | When it occurs |
|---|---|---|
| Best case | O(n log n) | Pivot always splits list into two equal halves |
| Average case | O(n log n) | Pivot splits roughly evenly most of the time |
| Worst case | O(n²) | Pivot is always the smallest or largest element |
The worst case — O(n²) — occurs when the list is already sorted and the first or last element is always chosen as pivot. A good pivot strategy (random or median-of-three) makes this practically impossible.
The log n factor comes from the recursion depth. With a balanced split, the list halves at each level, producing roughly log₂ n levels. At each level, O(n) work is done across all the partitions — giving O(n log n) total.
How is quicksort written in pseudocode?
PROCEDURE quickSort(list, low, high)
IF low < high THEN
pivotIndex ← partition(list, low, high)
quickSort(list, low, pivotIndex - 1)
quickSort(list, pivotIndex + 1, high)
END IF
END PROCEDURE
FUNCTION partition(list, low, high)
pivot ← list[high]
i ← low - 1
FOR j ← low TO high - 1
IF list[j] <= pivot THEN
i ← i + 1
SWAP(list[i], list[j])
END IF
END FOR
SWAP(list[i + 1], list[high])
RETURN i + 1
END FUNCTION
Call with quickSort(list, 0, LENGTH(list) - 1).
How does quicksort compare with merge sort and bubble sort?
| Algorithm | Average time | Worst time | Space | Stable? | In-place? |
|---|---|---|---|---|---|
| Quicksort | O(n log n) | O(n²) | O(log n) | No | Yes |
| Merge sort | O(n log n) | O(n log n) | O(n) | Yes | No |
| Bubble sort | O(n²) | O(n²) | O(1) | Yes | Yes |
Quicksort's advantages over merge sort: it sorts in place (no extra array needed) and its cache performance is better in practice. Merge sort's advantage: guaranteed O(n log n) worst case and it is stable (equal elements keep their original order). Bubble sort is rarely used for large datasets — it exists primarily as a teaching example.
In real systems, many languages use introsort: quicksort that switches to heapsort when recursion depth becomes too large, combining quicksort's average performance with heapsort's O(n log n) worst-case guarantee.
Frequently asked questions
Is quicksort in the GCSE Computer Science specification?
Quicksort is explicitly listed in several exam board specifications including AQA GCSE Computer Science (8525). You may be asked to trace its execution on a given list, explain the role of the pivot, describe the partition step, or compare its time complexity with other algorithms. Check your specific board's specification for the exact scope.
Why is quicksort called "quick"?
The name reflects its practical speed. Despite having the same O(n log n) average complexity as merge sort, quicksort tends to run faster on real data because it accesses memory sequentially (good cache behaviour) and requires no extra storage for a temporary array. Professor Tony Hoare, who invented quicksort in 1959, noted that the algorithm's constant factor is smaller than competing algorithms of the same order.
What happens when quicksort reaches a list of one element?
The base case of the recursion is when low >= high — meaning the sub-list has zero or one element. A single-element list is trivially sorted, so the function returns immediately without doing any work. This stopping condition is what prevents infinite recursion.
Can quicksort sort strings and not just numbers?
Yes — quicksort (and any comparison-based sort) works on any data type that has a defined ordering. Strings are compared lexicographically (dictionary order): "apple" < "banana" because 'a' < 'b'. The partitioning logic remains identical; only the comparison operator changes.
Want to trace quicksort on your own lists and get instant feedback? Professor Turing at aitutors.me will walk through every partition step with you.