Sorting Algorithms

Sorting is the classic lens for learning algorithm analysis: every method produces the same ordered output, but the cost of getting there ranges from O(n²) to O(n log n). Watching them side by side makes the trade-offs concrete.

The simple O(n²) sorts

Bubble sort repeatedly swaps adjacent out-of-order pairs; selection sort repeatedly picks the smallest remaining element; insertion sort grows a sorted prefix one element at a time. All three are quadratic in the worst case, but insertion sort shines on small or nearly-sorted inputs, where it approaches O(n).

The divide-and-conquer sorts

Merge sort splits the array in half, sorts each half and merges them, guaranteeing O(n log n) at the cost of extra memory. Quicksort partitions around a pivot and recurses; it is usually the fastest in practice thanks to cache locality, but a poor pivot can degrade it to O(n²). Heap sort builds a binary heap and repeatedly extracts the max, sorting in place in O(n log n) with no extra memory.

Stability & in-place

Two properties decide which sort fits a job: stability (equal keys keep their original order — merge and insertion sort are stable; quick and heap sort are not) and whether the sort works in place (no significant extra memory — quick and heap sort do; merge sort does not). Step through each below to feel the difference.