Sorting is the most-tested topic in placement DSA — not to write from scratch, but to compare. You should instantly recall each algorithm's time and space complexity, whether it is stable, and when each is the right choice.
Three speeds of sorting
The simple sorts (bubble, selection, insertion) are O(n²). The efficient comparison sorts (merge, heap) are O(n log n) guaranteed. Quicksort averages O(n log n) but degrades to O(n²) on bad pivots.
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Selection | O(n^2) | O(n^2) | O(n^2) | O(1) | No |
| Insertion | O(n) | O(n^2) | O(n^2) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n^2) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
⚡ The edge
- Memorise the table: simple sorts are O(n²); merge and heap are O(n log n) guaranteed; quicksort is O(n log n) on average but O(n²) on a sorted input with a naive pivot.
- When a problem says values are small integers in a known range, a non-comparison sort (counting / radix) can hit O(n).
Worked example
One pass of bubble sort on [5, 1, 4, 2]. What is the array after the first pass?
- Compare and swap adjacent out-of-order pairs, left to right.
- 5>1 swap -> [1,5,4,2]; 5>4 swap -> [1,4,5,2]; 5>2 swap -> [1,4,2,5].
- After one pass the largest element (5) has 'bubbled' to the end.
Answer: [1, 4, 2, 5] — the max is now at the end
Worked example
Why is merge sort O(n log n)?
- It splits the array in half repeatedly, giving about log n levels of division.
- At each level, merging all the pieces touches every element once — O(n) work per level.
- log n levels times O(n) per level gives O(n log n).
Answer: log n levels x O(n) merge work = O(n log n)
⚠ Watch out
- Stability matters when sorting by one key while preserving another's order — merge and insertion are stable; quick and heap are not.
- Quicksort's worst case O(n²) happens on already-sorted input with a poor pivot — use a random or median pivot.
- Counting/radix sort beats O(n log n) only for bounded integer ranges, and uses extra space.