What is Sorting
Sorting is the process of arranging a collection of items into a defined order — ascending, descending, alphabetical, or by any key you choose. It is one of the most studied problems in computer science because so many other operations depend on ordered data. Binary search requires a sorted input. Database indexes maintain sorted structures. Merge operations, deduplication, and ranking all start with a sort.
How it works
A comparison sort works by repeatedly comparing pairs of elements and swapping them until the entire collection is in order. The simplest example is bubble sort: scan the list, swap adjacent elements that are out of order, repeat until no swaps are needed. It works, but it is O(n^2) — too slow for large inputs.
Better algorithms exploit structure. Merge sort divides the list in half, sorts each half recursively, and merges the results in O(n) time. Quicksort picks a pivot, partitions elements around it, and recurses on the partitions. Both achieve O(n log n) average time.
There is a mathematical proof that no comparison-based sort can do better than O(n log n) in the worst case. Every comparison eliminates at most half the remaining possibilities, so sorting n items requires at least log2(n!) comparisons — which grows as O(n log n).
Non-comparison sorts like counting sort and radix sort bypass this bound by exploiting properties of the data (integers within a known range). They can achieve O(n) time, but only under specific constraints.
Sorting algorithms also differ in stability (whether equal elements keep their original order) and space (whether extra memory is needed). Merge sort is stable but uses O(n) space. Quicksort is in-place but not stable. These tradeoffs matter in practice.
Why it matters
Sorting is a prerequisite for efficient searching, merging, and reporting. Choosing the right sort for a given dataset — small vs. large, nearly sorted vs. random, memory-constrained vs. not — is a fundamental engineering decision. Understanding the O(n log n) bound tells you when you've hit the theoretical limit and when a specialized algorithm can do better.
See How Sorting Works for detailed walkthroughs of each algorithm.