Sorting Algorithms

Putting things in order

Sorting is the foundation of countless other algorithms — binary search needs a sorted array, databases sort to merge join, and schedulers sort by priority. Understanding the classic sort algorithms teaches you the difference between O(n²) and O(n log n), and why that gap matters.

The simple sorts — O(n²)

Bubble sort repeatedly walks the array, swapping adjacent out-of-order pairs until none remain. It is easy to teach but catastrophically slow on large inputs.

// Bubble sort: O(n²)
for (int i = 0; i < n; i++)
  for (int j = 0; j < n - 1; j++)
    if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);

Insertion sort builds the sorted portion one element at a time by inserting each new element into its correct place. It is still O(n²) worst case but O(n) on nearly-sorted input — which is why real libraries use it for small or nearly-sorted runs.

The efficient sorts — O(n log n)

Merge sort recursively splits the array in half, sorts each half, and merges the sorted halves. It is guaranteed O(n log n) in all cases and is stable (equal elements keep their original order), but it needs O(n) extra space.

mergeSort(left half)  → sorted
mergeSort(right half) → sorted
merge the two sorted halves

Quicksort picks a pivot, partitions the array into elements less than and greater than the pivot, and recursively sorts each side. It is O(n log n) on average and sorts in place, but its worst case is O(n²) when the pivot is consistently bad (e.g., already-sorted input with a naive pivot choice).

Stability

A sort is stable if equal-keyed elements preserve their input order. Stability matters when you sort by one field after another (e.g., sort by last name, then by first name) — the second sort must not scramble the first.

• Stable: merge sort, insertion sort, counting sort.
• Unstable: quicksort, heapsort, selection sort.

Most production sort implementations are hybrids. Python's Timsort and modern V8 use merge sort for large runs and insertion sort for small ones, getting the best of both worlds.

In-place vs not

An in-place sort uses O(1) extra memory (quicksort, heapsort). Merge sort is not in-place — it allocates a temporary array. In-place matters when memory is tight, as on embedded devices or huge datasets.