Sorting Algorithms

Sorting puts a sequence in order (e.g. by value or key). Different algorithms trade off time, space, and stability. Comparison-based sorts (e.g. merge sort, quicksort) use only comparisons; lower bound Ω(n log n) for general comparison sort. Merge sort: divide the list, sort each half, merge — O(n log n), stable, good when random access is costly. Quicksort: pick a pivot, partition, recurse — O(n log n) average, in-place, fast in practice. Bubble sort: repeatedly swap adjacent out-of-order pairs — O(n²), simple but slow. Bucket/count sorts use the structure of keys for linear time when keys are bounded. Choice depends on data size, memory, and whether stability matters.

Order matters for search (binary search needs sorted input), display (rankings, feeds), and prioritisation (what to do first). For small n or one-off lists, simple sorts are fine. For large or repeated sorts, use O(n log n) methods (merge, quicksort) or linear-time sorts when keys have structure. Avoid O(n²) on large inputs.

Sorting puts sequences in order. Comparison-based sorts have Ω(n log n) lower bound; merge sort and quicksort achieve O(n log n). Choose by scale, memory, and stability. Use sorting (or partial sort) for prioritisation, search prep, and ordered display.