Sorting algorithm

This article deals with sorting methods in computer science. For sorting methods in process engineering, see Technical sorting method.

In computer science, a sorting method is an algorithm that is used to sort a tuple (generally an array). The prerequisite is that a strict weak order ("less-than-equal") is defined on the set of elements, e.g. the lexicographic order of strings or the numerical order of numbers.

There are different sorting algorithms that work with different efficiencies in terms of time complexity (number of operations required) and space complexity (additional memory required in addition to the input array). The complexity of an algorithm is usually represented in Landau notation (see below expressions such as $\Theta (n\cdot \log(n))$ ). For some sorting methods, the time complexity depends on the initial ordering of the values in the array; one then distinguishes between best case (when the "preordering" is most favorable), average case (normal case), and worst case (worst case ~ the values are "maximally unfavorably preordered"). Often additional factors have to be taken into account that have an influence on time or space complexity, for example slow access to externally stored data, limited size of the main memory or similar.

A distinction is also made between stable and unstable sorting methods. Stable sorting methods are those that do not change the relative order of elements that are equivalent in terms of order, while unstable sorting methods do not guarantee this. For example, if a company's list of employees is ordered by last name and then sorted by age (in years), the (last name) order among employees of the same age will remain the same in a stable sorting procedure.

In addition, a distinction is made between sorting methods that work in-place (also in situ), i.e. the additional memory requirement is independent of the number of elements to be sorted (i.e. constant and usually low), and those for which it is dependent (out-of-place or ex situ).

And one also distinguishes between natural sorting algorithms, which work faster on presorted data than on unsorted data, and those that do not. Algorithms in which the control flow depends on the data are called adaptive, and correspondingly sorting methods that do not depend on the input data are called non-adaptive. Non-adaptive algorithms are thus particularly interesting for hardware implementations.

Manual sorting (e.g. of index cards) as well as electro-mechanical sorting methods (e.g. for punched cards) usually correspond to one of the software-based sorting methods described here, or mixed types.

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.