Sorting algorithm
Algorithm that reorders list elements into a specified order.
A sorting algorithm is an algorithm that puts elements of a list into an order, most frequently numerical or lexicographical order, in either ascending or descending order. Efficient sorting is important for optimizing the efficiency of other algorithms, such as search and merge algorithms, and for canonicalizing data and producing human-readable output. Formally, the output of any sorting algorithm must be in monotonic order and must be a permutation of the input, retaining all original elements. While some algorithms are designed for sequential access, the highest-performing ones assume data is stored in a structure allowing random access.
The sorting problem has attracted extensive research since the beginning of computing, due to the complexity of solving it efficiently despite its simple statement. Early sorting algorithms from around 1951 include the work of Betty Holberton on ENIAC and UNIVAC, and bubble sort was analyzed as early as 1956. Asymptotically optimal algorithms have been known since the mid-20th century, yet new algorithms continue to be invented, such as Timsort from 2002 and library sort from 2006. Comparison-based sorting algorithms have a fundamental requirement of a certain number of comparisons, while non-comparison algorithms like counting sort can achieve better performance.
Sorting algorithms are prevalent in introductory computer science, introducing concepts like big O notation, divide-and-conquer, data structures such as heaps and binary trees, randomized algorithms, best/worst/average case analysis, time–space tradeoffs, and upper and lower bounds. Sorting small arrays optimally or quickly remains an open research problem, with solutions only known for arrays with fewer than 20 elements. Optimal sorting on a parallel machine is also an open topic.
Classification is based on computational complexity (with good serial behavior typically O(n log n) and bad behavior O(n²)), memory usage (including in-place sorts requiring O(1) or O(log n) extra memory), recursion, stability (preserving the relative order of equal keys), whether the algorithm is a comparison sort, general method (e.g., insertion, exchange, selection, merging), serial or parallel operation, adaptability to presortedness, and whether it is online. Stability is important for preserving order over multiple sorts, such as when sorting student records first by name th
- definition
- Algorithm that reorders elements into monotonic order as a permutation of the input
- key_requirement
- Output must be in monotonic order and a permutation of the input
- asymptotically_optimal_known_since
- Mid-20th century
Lore & Background
From the beginning of computing, the sorting problem has attracted a great deal of research due to the complexity of solving it efficiently despite its simple statement. Among the early pioneers of sorting algorithms was Betty Holberton, who worked on the ENIAC and UNIVAC systems around 1951. Bubble sort was analyzed as early as 1956. While asymptotically optimal algorithms have been known since the mid-20th century, new algorithms continue to be developed, such as Timsort from 2002 and the library sort from 2006. Sorting algorithms are a staple of introductory computer science education, as their variety introduces core concepts like big O notation, divide-and-conquer strategies, data structures such as heaps and binary trees, randomized algorithms, best/worst/average case analysis, time–space tradeoffs, and upper and lower bounds. The problem of optimally sorting very small arrays (fewer than 20 elements) remains an open research area, as does optimal sorting on parallel machines. Sorting algorithms can be classified by computational complexity, with typical serial sorts achieving O(n log n) and parallel sorts reaching O(log² n), while worst-case behavior can be O(n²). They are also categorized by memory usage (including in-place algorithms requiring only O(1) or O(log n) extra space), recursion, stability (preserving the relative order of equal elements), whether they are comparison-based, and their general method (insertion, exchange, selection, merging). Exchange sorts include bubble sort and quicksort; selection sorts include cycle sort and heapsort. Adaptive algorithms account for presortedness in the input, and online algorithms like insertion sort can handle a constant stream of data. Stability is crucial when sorting data by multiple keys, ensuring that a later sort by one key does not disrupt the order established by an earlier sort on another key.
Reader's Guide
Sorting algorithms are fundamental to computer science, with their study providing a gentle introduction to core algorithm concepts such as big O notation, divide-and-conquer algorithms, data structures like heaps and binary trees, randomized algorithms, and time–space tradeoffs. Comparison sorting algorithms have a fundamental requirement of n log n - 1.4427n + O(log n) comparisons, while non-comparison sorts like counting sort can have better performance. Sorting small arrays optimally remains an open research problem, with solutions only known for very small arrays (fewer than 20 elements). Stability is important for preserving order over multiple sorts on the same data set, as stable sorting algorithms maintain the relative order of records with equal keys. Sorting algorithms are classified by computational complexity, memory usage, recursion, stability, whether they are comparison sorts, general method, serial or parallel operation, adaptability, and whether they are online.
Did You Know?
- Sorting small arrays optimally is still an open research problem, with solutions only known for arrays with fewer than 20 elements.
Frequently Asked Questions
What is a sorting algorithm?
A sorting algorithm is a procedure that takes a list of elements and rearranges them into a consistent ascending or descending sequence, yielding a permutation of the original input.
What are the two core requirements of a valid sorting algorithm?
Its output must be in monotonic order (either fully ascending or fully descending) and must be a permutation of the input, meaning no elements are added, removed, or duplicated.
Why are sorting algorithms important in complexity theory?
Efficient sorting underpins the performance of many other algorithms such as search and merge routines, and it is essential for canonicalizing data and producing human-readable output, making it a foundational benchmark in the field.
More in Complexity Theory 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record