A sorting algorithm takes a collection of items and rearranges them into a defined order, such as numbers from smallest to largest or words alphabetically. Sorting is one of the oldest and most thoroughly studied problems in computing, and Donald Knuth devoted an entire volume of The Art of Computer Programming, Volume 3, to “Sorting and Searching.”
Most general sorting methods work by comparing pairs of items and deciding which should come first. The cost of a sort is usually measured by counting these comparisons and the data movements they cause. Knuth’s Volume 3 analyzes many such methods in detail, treating the running time and storage of each as quantities to be measured rather than guessed.
Sorting algorithms differ along several axes that recur throughout the field. Time and space trade off against each other, so a method that uses extra memory may run faster, while an “in place” method saves memory at some cost in speed. A method is called stable when it preserves the original order of items that compare as equal, a property that matters when records are sorted on more than one key.
A central result is that any sorting method based only on pairwise comparisons must, in the worst case, perform on the order of n log n comparisons to sort n items. Methods such as Hoare’s Quicksort, introduced in The Computer Journal in 1962, approach this bound in typical use, which is why the n log n figure is treated as the practical target for comparison-based sorting.