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.
- 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.
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