AlegsaOnline.com

Sorting algorithm

A sorting algorithm arranges elements of a collection in a prescribed order. Covers types, properties (stability, in-place), common algorithms, complexity bounds, history, and practical applications.

Author: Leandro Alegsa Creation date: November 13, 2022 Last updated: June 3, 2026

en.wikipedia.org · CC BY-SA 2.5

Overview

A sorting algorithm is a procedure that rearranges the elements of a collection—such as numbers, strings, or records—into a specified order. Most often this means ascending or descending numeric order, or lexicographic order for text. Beyond tidy presentation, sorted data enables faster search, efficient duplicate elimination and easier merging of datasets. Sorting is a fundamental building block in computer science and underpins many higher-level operations in databases, user interfaces and numerical computations.

Key characteristics

Sorting methods are commonly described by several attributes that affect suitability for particular tasks:

Time complexity: how running time scales with the number of items, often expressed in Big O notation (for example O(n log n) or O(n²)).
Space usage: whether the algorithm works in-place (constant extra memory) or requires additional memory proportional to the input size.
Stability: whether equal elements preserve their original relative order after sorting; stable sorts are important when multiple keys are involved.
Adaptivity and online behavior: whether the algorithm takes advantage of existing order in the input, or can process items as they arrive.
Comparison vs non-comparison: most general-purpose sorts compare items; others (counting, radix) exploit numeric properties to achieve linear-time behavior under certain conditions.

Common algorithms and their profiles

A selection of widely used sorting techniques illustrates trade-offs between simplicity, performance and memory use:

Insertion sort — simple, adaptive and stable; efficient on small or nearly-sorted inputs but O(n²) worst-case time.
Selection sort and bubble sort — conceptually simple but generally inefficient for large datasets (O(n²)).
Mergesort — stable and O(n log n) time; requires additional memory for merging but is well-suited to external (disk-based) sorting.
Quicksort — typically very fast in practice with average O(n log n) time and low memory overhead, but worst-case O(n²) unless safeguards are added.
Heapsort — O(n log n) worst-case and in-place, though not stable; useful when guaranteed worst-case bounds are required.
Counting sort, radix sort — non-comparison methods that can run in linear time for integer keys or fixed-length strings under suitable constraints.

History and development

Sorting predates digital computers: people physically arranged cards and records long before electronic machines. With the arrival of stored-program computers, researchers formalized and analyzed many techniques. Theoretical work established lower bounds for comparison-based sorting, showing that any comparison sort requires on the order of n log n comparisons in the worst case. Practical refinements and hybrid approaches—such as introspective algorithms that switch strategies based on workload—have been developed to combine theoretical guarantees with good real-world performance.

Practical applications and examples

Sorted collections are everywhere: database query engines sort result sets for grouping or range queries, search algorithms assume sorted inputs to improve speed, and user interfaces present lists in alphabetical or numeric order. External sorting methods (for example multi-way merge sorts) are tailored to datasets too large to fit in memory and are central to large-scale data processing. Modern programming language libraries typically provide highly tuned, stable, or hybrid sorts as standard utilities to serve general needs.

Notable distinctions and considerations

Choosing a sort depends on input size, memory limits, stability requirements and data characteristics. Cache behavior, branch prediction, and small-constant factors mean that algorithms with the same asymptotic complexity can perform very differently in practice. For specialized uses, stable multi-key sorts, adaptive sorts for nearly-sorted data, and parallel or external sorts for very large collections are available. For a concise technical reference and implementations, see Further reading.

Comparison based sorting

General procedures are based on the pairwise comparison of the elements to be sorted as to whether one element is "less than", "greater than" or "equal(great)" to the other element. Complexity analysis assumes that the effort required to compare two elements is constant.

Sorting method	Best-case scenario	Average case	Worst-case scenario	Stable	Additional memory requirements
Binary Tree Sort (height-balanced)	$\Theta (n\cdot \log(n))$ 1!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	yes	$\Theta (n)$
Binary Tree Sort	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n^{2})$ 2!	yes	$\Theta (n)$
Bubblesort	$\Theta (n)$ 1!	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	yes	- –
Combsort	$\Theta (n\cdot \log(n))$ 1.00001!	${\mathcal {O}}(n^{2})$ 2!	${\mathcal {O}}(n^{2})$ 2!	no	- –
Gnomesort	$\Theta (n)$ 1!	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	yes	- –
Heapsort	$\Theta (n)$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	no	- –
Insertion location	$\Theta (n)$ 1!	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	yes	- –
Introsort	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	no	- –
merge insertion	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	yes	- –
Mergesort	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	yes	Implementation on linked list: in-place usual implementations (on array): $\Theta (n)$ There is in-place on array, but then time complex. = n * (log n) * (log n) .
Natural Mergesort	$\Theta (n)$ 1!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	yes	- –
Quicksort	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n^{2})$ 2!	no	$\Theta (\log(n))$ , common implementations usually require more
Selectionsort	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	no	- –
Shakersort (Cocktailsort)	$\Theta (n)$ 1!	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	yes	- –
Shellsort	${\mathcal {O}}(n\cdot \log(n)^{2})$ 1.00001!	${\mathcal {O}}(n\cdot \log(n)^{2})$ 1.00002!	${\mathcal {O}}(n\cdot \log(n)^{2})$ 1.00002!	no	- –
Smoothsort	$\Theta (n)$ 1!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	no	- –
Stoogesort	$\Omega (n^{2,7})$ 2.71!	$\Omega (n^{2,7})$ 2.71!	$\Omega (n^{2,7})$ 2.71!	no	- –
Swap Sort	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	$\Theta (n^{2})$ 2!	- –	- –
Timsort	$\Theta (n)$ 1!	$\Theta (n\cdot \log(n))$ 1.00001!	$\Theta (n\cdot \log(n))$ 1.00001!	yes	- –
Bogosort	$\Theta (n)$ 1!	${\mathcal {O}}(n\cdot n!)$ 10000!	${\mathcal {O}}(n\cdot n!)$ 10000!	no	- –
Slowsort	$\Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)$	$\Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)$	$\Omega \left(n^{\frac {\log(n)}{(2+\varepsilon )}}\right)$	no	- –

↑ ^{a b} For the stable version, see the remark in the article Binary Tree Sort.
↑ ^{a b c} For the (worst case) best known distance sequence.
↑ ^{a b} Expected runtime.
↑ ^{a b c} For any ε $\varepsilon >0$ , see Slowsort.

Non-comparison based sorting

With sorting methods that are not based on comparisons, i.e. in which the objects to be sorted are not compared with each other for "less than", "greater than" or "equal to", it can be achieved with appropriately conditioned input that the time required increases only linearly with the number of elements to be sorted. For large numbers of data sets to be sorted, these algorithms are superior to comparison-based methods, provided they can be applied (because of the additional memory requirements). However, they can only be used for numeric data types (or under the condition that the data type can be mapped to numeric values of the same order in an acceptable effort). It is implicitly assumed that the length of the key is limited, so that its utilization is possible in constant time. The lowering of the time complexity from the number of elements is bought by an additional time dependency variable (usually the key length or the number of possible key values), often also by considerable additional memory requirements.

Sorting method	Time	Stable	Additional memory requirements
Bucketsort	${\mathcal {O}}\left(n+k\right)$	yes	${\mathcal {O}}\left(n+k\right)$
Counting location	${\mathcal {O}}\left(n+k\right)$	yes	${\mathcal {O}}\left(n+k\right)$
Radix location	${\mathcal {O}}\left(n\cdot l\right)$	yes	${\mathcal {O}}\left(n\right)$
MSD Radixsort	${\mathcal {O}}\left(n\cdot l\right)$	no	${\mathcal {O}}\left(1\right)$ , in-place
Flashsort	${\mathcal {O}}\left(n\right)\,..\,{\mathcal {O}}\left(n^{2}\right)$	no	${\mathcal {O}}\left(1\right)$

Where represents the number of elements, represents the number of possible values, and represents the number of digits of the longest key.

Questions and Answers

Q: What is a sorting algorithm?

A: A sorting algorithm is an algorithm that arranges the elements of a collection in a specific order.

Q: How are numbers usually sorted?

A: Numbers are usually sorted by their value.

Q: How are words typically sorted?

A: Words are typically sorted by their lexicographic order, which means the order they would appear in a dictionary or phone book.

Q: Why is efficient sorting important?

A: Efficient sorting is important because it makes it easier to find an element in a sorted collection and to merge a new element into a sorted collection.

Q: Can all sorting algorithms be applied in all cases?

A: No, not all sorting algorithms can be applied in all cases.

Q: What is an example of a case where not all sorting algorithms can be applied?

A: An example might be when records can only be read sequentially, such as when they are stored on a tape.

Q: Why might efficient sorting be important for merging new elements into a sorted collection?

A: Efficient sorting makes it easier to merge new elements into a sorted collection because it helps maintain the sorted order of the collection.

Author

AlegsaOnline.com - Sorting algorithm - Leandro Alegsa

Creation date: November 13, 2022
Last updated: June 3, 2026

URL: https://en.alegsaonline.com/art/91990