Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order.

Uses your system voice; voice and rate in settings.

≈ 3 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order and lexicographical order, and either ascending order or descending order.

Efficient sorting is important for optimizing the efficiency of other algorithms (such as search and merge algorithms) that require input data to be in sorted lists. Sorting is also often useful for canonicalizing data and for producing human-readable output.

Formally, the output of any sorting algorithm must satisfy two conditions: The output is in monotonic order (each element is no smaller/larger than the previous element, according to the required order). The output is a permutation (a reordering, yet retaining all of the original elements) of the input.

Although some algorithms are designed for sequential access, the highest-performing algorithms assume data is stored in a data structure which allows random access. One application for stable sorting algorithms is sorting a list using a primary and secondary key.

For example, suppose we wish to sort a hand of cards such that the suits are in the order clubs (♣), diamonds ( ♦ ), hearts ( ♥ ), spades (♠), and within each suit, the cards are sorted by rank. This can be done by first sorting the cards by rank (using any sort), and then doing a stable sort by suit: Within each suit, the stable sort preserves the ordering by rank that was already done.

This idea can be extended to any number of keys and is utilised by radix sort. The same effect can be achieved with an unstable sort by using a lexicographic key comparison, which, e.g., compares first by suit, and then compares by rank if the suits are the same.

In Algorithms and Data Structures Niklaus Wirth gives a comparison of the running time of several of the popular algorithms on the Lilith computer. 15 Sorting Algorithms in 6 Minutes (Youtube) – Visualization and "audibilization" of 15 Sorting Algorithms in 6 Minutes.

A036604 sequence in OEIS database titled "Sorting numbers: minimal number of comparisons needed to sort n elements" – Performed by Ford–Johnson algorithm. Sorting Algorithms Used on Famous Paintings (Youtube) – Visualization of Sorting Algorithms on Many Famous Paintings.

A Comparison of Sorting Algorithms – Runs a series of tests of 9 of the main sorting algorithms using Python timeit and Google Colab.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1358157912 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001358157912 · captured 2026-06-06 · ledger · version history

Cite this page as: encyclopegia.org, “Sorting algorithm”, snapshot enwiki-001358157912. https://encyclopegia.org/a/sorting-algorithm

Sources cited in this revision

13 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.