Sorting Algorithms Explained: Bubble, Selection, Insertion, Merge and Quick Sort
Sorting is the classic algorithms topic because it shows, in one problem, how different ideas lead to very different speeds. Exams usually ask you to trace an algorithm on a small array, state its complexity, or compare two of them. This guide prepares you for all three.
1. The three simple sorts (O(n²))
Bubble sort
Repeatedly walk through the array, swapping neighbours that are in the wrong order. After each pass, the largest remaining value has "bubbled" to the end. With an early-exit check (stop if a pass makes no swaps), an already-sorted array finishes in one pass.
Trace on [5, 1, 4, 2], pass 1: (5,1) swap → [1,5,4,2]; (5,4) swap → [1,4,5,2]; (5,2) swap → [1,4,2,5]. The 5 is now in place.
Selection sort
Find the smallest value in the unsorted part and swap it into the first unsorted position. It always makes about n²/2 comparisons, even on sorted input, but at most n − 1 swaps.
Insertion sort
Build the sorted part one element at a time: take the next value and shift larger values right until it fits. It is very fast on small or nearly-sorted arrays (close to O(n)), which is why real libraries use it for small pieces.
2. Merge sort (O(n log n))
Merge sort uses divide and conquer: split the array in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element.
[38, 27, 43, 3] → split into [38, 27] and [43, 3] → sorted halves [27, 38] and [3, 43] → merge → [3, 27, 38, 43].
It is always O(n log n), even in the worst case, and it is stable. The cost is extra memory: merging needs an auxiliary array of size n, so space is O(n).
3. Quick sort (average O(n log n))
Quick sort picks a pivot, partitions the array so smaller values go left and larger values go right, then recursively sorts each side. The pivot ends up in its final position after partitioning.
On average it is O(n log n) and very fast in practice because it sorts in place. Its weakness: if the pivot is always the smallest or largest value (for example, the last element of an already-sorted array), the split is lopsided and it degrades to O(n²). Choosing a random or median-of-three pivot avoids this in practice.
4. Comparison table
| Algorithm | Best | Average | Worst | Extra space | Stable? |
|---|---|---|---|---|---|
| Bubble (with early exit) | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | 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²) | O(log n) stack | No |
A sort is stable if equal values keep their original order. That matters when sorting records, for example students already sorted by name and then sorted by marks.
5. How to trace in an exam
- Write the array after every pass (or every merge / partition), on its own line.
- For quick sort, state the pivot and show the array after each partition.
- For merge sort, draw the split tree first, then merge from the bottom up.
- Count comparisons or swaps only if the question asks; read carefully which it wants.
- Double-check the final array is actually sorted. It sounds obvious, but slips are common under time pressure.