Editing Sorting algorithm (section)

== Comparison of algorithms ==
This analysis assumes that the length of each key is constant and that all comparisons, swaps and other operations can proceed in constant time.

Legend:
* {{mvar|n}} is the number of records to be sorted.
* Comparison column has the following ranking classifications: "Best", "Average" and "Worst" if the [[time complexity]] is given for each case. 
* "Memory" denotes the amount of additional storage required by the algorithm.
* The run times and the memory requirements listed are inside [[big O notation]], hence the base of the logarithms does not matter.
* The notation {{math|log<sup>2</sup> ''n''}} means {{math|(log ''n'')<sup>2</sup>}}.

=== Comparison sorts ===
Below is a table of [[comparison sort]]s. [[Analysis of algorithms|Mathematical analysis]] demonstrates a comparison sort cannot perform better than {{math|''O''(''n'' log ''n'')}} on average.<ref>{{citation |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ron Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein|title=Introduction To Algorithms|url=https://books.google.com/books?id=NLngYyWFl_YC|edition=3rd |place=Cambridge, MA |publisher=The MIT Press |year=2009 |isbn=978-0-262-03293-3| page=167 |chapter=8}}</ref>

{|class="wikitable sortable"
|+ [[Comparison sort]]s
! Name !! Best !! Average  !! Worst !! Memory !! Stable 
!In-place!! Method !! Other notes
<!-- Sorting Guide:
     00 = constant
     05 = log n
     10 = n^c, 0 < c < 1
     15 = n
     20 = n*log n or log n!
     23 = n*(log n)^2 or n^c, 1 < c < 2
     25 = n^2
     30 = n^c, c > 2
     40 = c^n, c > 1
     45 = n!
     50 = other -->
|- align="center"
|nowrap| [[In-place merge sort]]
| —
| —
|style="background:#ffd"| {{Sort|23|<math>n \log^2 n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#dfd"| Yes
|style="background:#dfd"| Yes
| Merging
|align="left"| Can be implemented as a stable sort based on stable in-place merging.<ref>{{Cite journal | doi = 10.1093/comjnl/35.6.643| title = Fast Stable Merging and Sorting in Constant Extra Space| journal = [[Comput. J.]]| volume = 35| issue = 6| pages = 643–650
| date = December 1992| last1 = Huang | first1 = B. C. | last2 = Langston | first2 = M. A.| citeseerx=10.1.1.54.8381}}</ref>
|- align="center"
| [[Heapsort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#fdd"| No
|style="background:#dfd"| Yes
| Selection
|align="left"|
|- align="center"
| [[Introsort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#ffd"| {{Sort|05|<math>\log n</math>}}
|style="background:#fdd"| No
|
| Partitioning & Selection
|align="left"| Used in several [[Standard Template Library|STL]] implementations.
|- align="center"
| [[Merge sort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| Yes
|style="background:#fdd"| No
| Merging
|align="left"| [[Merge sort#Parallel merge sort|Highly parallelizable]] (up to {{math|''O''(log ''n'')}} using the Three Hungarians' Algorithm).<ref>{{Cite conference | doi = 10.1145/800061.808726| title = An {{math|O(n log n)}} sorting network| work = Proceedings of the fifteenth annual ACM symposium on Theory of computing | conference = [[Symposium on Theory of Computing|STOC]] '83| pages = 1–9| year = 1983| last1 = Ajtai | first1 = M. |author-link1 = Miklós Ajtai| last2 = Komlós | first2 = J. |author-link2 = János Komlós (mathematician)| last3 = Szemerédi | first3 = E. |author-link3 = Endre Szemerédi| isbn = 0-89791-099-0}}</ref>
|- align="center"
| [[Tournament sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}<ref>{{cite web|url=http://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf|author=Prof. E. Rahm|title=Sortierverfahren|website=Dbs.uni-leipzig.de|access-date=1 March 2022|archive-date=23 August 2022|archive-url=https://web.archive.org/web/20220823155525/https://dbs.uni-leipzig.de/skripte/ADS1/PDF4/kap4.pdf|url-status=live}}</ref>}}
| style="background:#fdd" | No
|
| Selection
| align="left" | Variation of Heapsort.
|- align="center"
| [[Tree sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math><wbr/>(balanced)}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
| style="background:#fdd" | No
| Insertion
| align="left" | When using a [[self-balancing binary search tree]].
|- align="center"
| [[Block sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#dfd"| Yes
|
| Insertion & Merging
|align=left| Combine a block-based {{tmath|O(n)}} in-place merge algorithm<ref>{{Cite conference | doi = 10.1007/978-3-540-79228-4_22| title = Ratio Based Stable In-Place Merging| work = Theory and Applications of Models of Computation| conference = [[International Conference on Theory and Applications of Models of Computation|TAMC]] 2008| volume = 4978| pages = 246–257| series = [[LNCS]]| year = 2008| last1 = Kim | first1 = P. S. | last2 = Kutzner | first2 = A. | isbn = 978-3-540-79227-7| citeseerx = 10.1.1.330.2641}}</ref> with a [[Merge sort#Bottom-up implementation|bottom-up merge sort]].
|- align="center"
| [[Smoothsort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Selection
| align="left" | An [[adaptive sort|adaptive]] variant of heapsort based upon the [[Leonardo number|Leonardo sequence]] rather than a traditional [[binary heap]].
|- align="center"
| [[Timsort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
|
| Insertion & Merging
| align="left" | Makes ''n-1'' comparisons when the data is already sorted or reverse sorted.
|- align="center"
| [[Patience sorting]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | No
|
| Insertion & Selection
| align="left" | Finds all the [[longest increasing subsequence]]s in {{math|''O''(''n'' log ''n'')}}.

|- align="center"
| [[Cubesort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
|
| Insertion
| align="left" | Makes ''n-1'' comparisons when the data is already sorted or reverse sorted.

|- align="center"
| [[Quicksort]]
|style="background:#ffd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n \log n</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#fdd"| No
|style="background:#fdd"| No
| Partitioning
|align="left"| Quicksort can be done in-place with {{math|''O''(log ''n'')}} stack space.<ref>{{cite book|last=Sedgewick|first=Robert|author-link=Robert Sedgewick (computer scientist)|title=Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4|url=https://books.google.com/books?id=ylAETlep0CwC|access-date=27 November 2012|edition=3|date=1 September 1998|publisher=Pearson Education|isbn=978-81-317-1291-7}}</ref><ref name=sedgewickQsortPaper>{{Cite journal | last1 = Sedgewick | first1 = R. | author-link1 = Robert Sedgewick (computer scientist)| title = Implementing Quicksort programs | doi = 10.1145/359619.359631 | journal = [[Comm. ACM]] | volume = 21 | issue = 10 | pages = 847–857 | year = 1978 | s2cid = 10020756 }}</ref>

|- align="center"
| [[Library sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#dfd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" |{{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | No
| style="background:#fdd" | No
| Insertion
| align="left" |Similar to a gapped insertion sort. It requires randomly permuting the input to warrant with-high-probability time bounds, which makes it not stable.

|- align="center"
| [[Shellsort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#ffd" | {{Sort|23|<math>n^{4/3}</math>}}
| style="background:#ffd" | {{Sort|23|<math>n^{3/2}</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Insertion
| align="left" | Small code size.

|- align="center"
| [[Comb sort]]
| style="background:#ffd" | {{Sort|20|<math>n \log n</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Exchanging
| align="left" | Faster than bubble sort on average.

|- align="center"
| [[Insertion sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
|style="background:#dfd"| {{Sort|00|1}}
|style="background:#dfd"| Yes
|style="background:#dfd"| Yes
| Insertion
|align=left| {{math|''O''(''n'' + ''d'')}}, in the worst case over sequences that have ''d'' [[Inversion (discrete mathematics)|inversions]].

|- align="center"
| [[Bubble sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes<!-- Disputed: No. Equal values are never swapped, so they never get out of order -->
| style="background:#dfd" | Yes
| Exchanging
| align="left" | Tiny code size.

|- align="center"
| [[Cocktail shaker sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes
|
| Exchanging
| align="left" |A variant of Bubblesort which deals well with small values at end of list

|- align="center"
| [[Gnome sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes
|
| Exchanging
| align="left" | Tiny code size.

|- align="center"
| [[Odd–even sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#dfd" | Yes
|
| Exchanging
| align="left" | Can be run on parallel processors easily.

|- align="center"
| [[Pancake sorting|Simple pancake sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Selection
|align="left"| A variant of selection sort that uses reversals, instead of just swapping the two items, after each selection scan.

|- align="center"
| [[Strand sort]]
| style="background:#dfd" | {{Sort|15|{{mvar|n}}}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|15|{{mvar|n}}}}
| style="background:#dfd" | Yes
|
| Selection
| align="left" |

|- align="center"
| [[Selection sort]]
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
| style="background:#dfd" | Yes
| Selection
| align="left" | Alternate Stable version, with {{tmath|O(n)}} extra space, when using linked lists, or when made as a variant of Insertion Sort instead of swapping the two items.<ref>{{cite web|url=http://www.algolist.net/Algorithms/Sorting/Selection_sort|title=SELECTION SORT (Java, C++) – Algorithms and Data Structures|website=Algolist.net|access-date=14 April 2018|archive-date=9 December 2012|archive-url=https://web.archive.org/web/20121209184535/http://www.algolist.net/Algorithms/Sorting/Selection_sort|url-status=live}}</ref>

|- align="center"
| [[Exchange sort]]
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
|
| Exchanging
| align="left" | Tiny code size.

|- align="center"
| [[Cycle sort]]
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#fdd" | {{Sort|25|<math>n^2</math>}}
| style="background:#dfd" | {{Sort|00|1}}
| style="background:#fdd" | No
| style="background:#dfd" | Yes
| Selection
| align="left" | In-place with theoretically optimal number of writes.
|}

=== Non-comparison sorts ===
The following table describes [[integer sorting]] algorithms and other sorting algorithms that are not [[comparison sort]]s. These algorithms are not limited to [[Big O notation|''Ω''(''n'' log ''n'')]] unless meet unit-cost [[random-access machine]] model as described below. <ref>{{citation |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson |last3=Rivest |first3=Ronald L. |author3-link=Ron Rivest |last4=Stein |first4=Clifford |author4-link=Clifford Stein|title=Introduction To Algorithms|url=https://books.google.com/books?id=NLngYyWFl_YC|edition=2nd |place=Cambridge, MA |publisher=The MIT Press |year=2001 |isbn=0-262-03293-7| page=165 |chapter=8}}</ref> 

* Complexities below assume {{mvar|n}} items to be sorted, with keys of size {{mvar|k}}, digit size {{mvar|d}}, and {{mvar|r}} the range of numbers to be sorted. 
* Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that {{math|''n'' ≪ 2<sup>''k''</sup>}}, where ≪ means "much less than". 
* In the unit-cost [[random-access machine]] model, algorithms with running time of <big><big><math>\scriptstyle n \cdot \frac{k}{d}</math>,</big></big> such as radix sort, still take time proportional to <small><big>{{math|Θ(''n'' log ''n'')}}</big></small>, because {{mvar|n}} is limited to be not more than <big><math>2^\frac{k}{d}</math>,</big> and a larger number of elements to sort would require a bigger {{mvar|k}} in order to store them in the memory.<ref>{{cite journal |first=Stefan |last=Nilsson |title=The Fastest Sorting Algorithm? |journal=[[Dr. Dobb's]] |year=2000 |url=http://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062 |access-date=2015-11-23 |archive-date=2019-06-08 |archive-url=https://web.archive.org/web/20190608084350/http://www.drdobbs.com/architecture-and-design/the-fastest-sorting-algorithm/184404062 |url-status=live }}</ref>
* 
{|class="wikitable sortable"
|+ Non-comparison sorts
! Name !! Best !! Average !! Worst !! Memory !! Stable !! {{math|''n'' ≪ 2<sup>''k''</sup>}} !! Notes
|- align="center"
| [[Pigeonhole sort]]
| —
|style="background:#dfd"| <math>n + 2^k</math>
|style="background:#dfd"| <math>n + 2^k</math>
| <math>2^k</math>
| {{Yes}}
| {{Yes}}
|align="left"| Cannot sort non-integers.
|- align="center"
| [[Bucket sort]] (uniform keys)
| —
|style="background:#dfd"| <math>n+k</math>
|style="background:#fdd"| <math>n^2 \cdot k</math>
| <math>n \cdot k</math>
| {{Yes}}
| {{No}}
|align="left"| Assumes uniform distribution of elements from the domain in the array.<ref name="clrs">{{Introduction to Algorithms|edition=2}}</ref>
Also cannot sort non-integers.
|- align="center"
| [[Bucket sort]] (integer keys)
| —
|style="background:#dfd"| <math>n+r</math>
|style="background:#dfd"| <math>n+r</math>
| <math>n+r</math>
| {{Yes}}
| {{Yes}}
|align="left"| If ''r'' is {{tmath|O(n)}}, then average time complexity is {{tmath|O(n)}}.<ref name="gt">{{cite book
 | last1 = Goodrich | first1 = Michael T. | author1-link = Michael T. Goodrich
 | last2 = Tamassia | first2 = Roberto | author2-link = Roberto Tamassia
 | contribution = 4.5 Bucket-Sort and Radix-Sort
 | pages = 241–243
 | publisher = John Wiley & Sons
 | title = Algorithm Design: Foundations, Analysis, and Internet Examples
 | year = 2002
 | isbn = 978-0-471-38365-9}}</ref>
|- align="center"
| [[Counting sort]]
| —
|style="background:#dfd"| <math>n+r</math>
|style="background:#dfd"| <math>n+r</math>
| <math>n+r</math>
| {{Yes}}
| {{Yes}}
|align="left"| If ''r'' is {{tmath|O(n)}}, then average time complexity is {{tmath|O(n)}}.<ref name="clrs" />
|- align="center"
| [[Radix sort#Least significant digit radix sorts|LSD Radix Sort]]
|style="background:#dfd"| <math>n</math>
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
| <math>n + 2^d</math>
| {{Yes}}
| {{No}}
|align="left"|<math>\frac{k}{d}</math> recursion levels, 2<sup>''d''</sup> for count array.<ref name="clrs" /><ref name="gt" />
Unlike most distribution sorts, this can sort non-integers.
|- align="center"
| [[Radix sort#Most significant digit radix sorts|MSD Radix Sort]]
| —
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
| <math>n + 2^d</math>
| {{Yes}}
| {{No}}
|align="left"| Stable version uses an external array of size {{mvar|n}} to hold all of the bins.
Same as the LSD variant, it can sort non-integers.
|- align="center"
| [[Radix sort#Most significant digit radix sorts|MSD Radix Sort]] (in-place)
| —
|style="background:#dfd"| <math>n \cdot \frac{k}{1}</math>
|style="background:#dfd"| <math>n \cdot \frac{k}{1}</math>
| <math>2^1</math>
| {{No}}
| {{No}}
|align="left"| d=1 for in-place, <math>k/1</math> recursion levels, no count array.
|- align="center"
| [[Spreadsort]]
|style="background:#dfd"| {{mvar|n}}
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
|style="background:#dfd"| <math>n \cdot \left( {\frac{k}{s} + d} \right)</math>
| <math>\frac{k}{d} \cdot 2^d</math>
| {{No}}
| {{No}}
|align="left"| Asymptotic are based on the assumption that {{math|''n'' ≪ 2<sup>''k''</sup>}}, but the algorithm does not require this.
|- align="center"
| [[Burstsort]]
| —
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
| <math>n \cdot \frac{k}{d}</math>
| {{No}}
| {{No}}
|align="left"| Has better constant factor than radix sort for sorting strings. Though relies somewhat on specifics of commonly encountered strings.
|- align="center"
| [[Flashsort]]
|style="background:#dfd"| {{mvar|n}}
|style="background:#dfd"| <math>n+r</math>
|style="background:#fdd"| <math>n^2</math>
| {{mvar|n}}
| {{No}}
| {{No}}
|align="left"| Requires uniform distribution of elements from the domain in the array to run in linear time. If distribution is extremely skewed then it can go quadratic if underlying sort is quadratic (it is usually an insertion sort). In-place version is not stable.
|- align="center"
| [[Postman sort]]
| —
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
|style="background:#dfd"| <math>n \cdot \frac{k}{d}</math>
| <math>n+2^d</math>
| —
| {{No}}
|align="left"| A variation of bucket sort, which works very similarly to MSD Radix Sort. Specific to post service needs.
|- align="center"
| [[Recombinant sort]]
| style="background:#dfd" | {{Sort|25|<math>n+r</math>}}
| style="background:#dfd" | {{Sort|25|<math>n+r</math>}}
| style="background:#dfd" | {{Sort|25|<math>n+r</math>}}
| style="background:#fdd" | {{Sort|10|<math>n  k</math>}}
| {{No}}
| {{No}}
| Hashing, Counting, Dynamic Programming, Multidimensional data
|
|}

[[Samplesort]] can be used to parallelize any of the non-comparison sorts, by efficiently distributing data into several buckets and then passing down sorting to several processors, with no need to merge as buckets are already sorted between each other.

=== Others ===
Some algorithms are slow compared to those discussed above, such as the [[bogosort]] with unbounded run time and the [[stooge sort]] which has ''O''(''n''<sup>2.7</sup>) run time. These sorts are usually described for educational purposes to demonstrate how the run time of algorithms is estimated. The following table describes some sorting algorithms that are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements.

{|class="wikitable sortable"
! Name !! Best !! Average !! Worst !! Memory !! Stable !! Comparison !! Other notes
|- align="center"
| [[Bead sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#ffd"| {{Sort|23|{{mvar|S}}}}
|style="background:#ffd"| {{Sort|23|{{mvar|S}}}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}
| {{N/A}}
| {{No}}
| align="left"| Works only with positive integers. Requires specialized hardware for it to run in guaranteed {{tmath|O(n)}} time. There is a possibility for software implementation, but running time will be {{tmath|O(S)}}, where {{mvar|S}} is the sum of all integers to be sorted; in the case of small integers, it can be considered to be linear.
|- align="center"
| [[Merge-insertion sort]]
| {{Sort|21|<math>n\log n</math><br />comparisons}}
| {{Sort|21|<math>n\log n</math><br />comparisons}}
| {{Sort|21|<math>n\log n</math><br />comparisons}}
| {{Sort|21|Varies}}
| {{No}}
| {{Yes}}
|align="left"| Makes very few comparisons worst case compared to other sorting algorithms. 
Mostly of theoretical interest due to implementational complexity and suboptimal data moves.
|- align="center"
| "I Can't Believe It Can Sort"<ref>{{cite arXiv |last1=Fung |first1=Stanley P. Y. |title=Is this the simplest (and most surprising) sorting algorithm ever? |eprint=2110.01111 |date=3 October 2021|class=cs.DS }}</ref>
|style="background:#fdd"| {{Sort|25|{{mvar|<math>n^2</math>}}}}
|style="background:#fdd"| {{Sort|25|{{mvar|<math>n^2</math>}}}}
|style="background:#fdd"| {{Sort|25|{{mvar|<math>n^2</math>}}}}
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align="left"| Notable primarily for appearing to be an erroneous implementation of either [[Insertion Sort]] or [[Sorting algorithm#Exchange sort|Exchange Sort]].
|- align="center"
| [[Spaghetti sort|Spaghetti (Poll) sort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#fdd"| {{Sort|25|<math>n^2</math>}}<!-- space should reflect amount of spaghetti needed; one rod must be at least n units long; n rods are needed. -->
| {{Yes}}
| Polling
|align="left"| This is a linear-time, analog algorithm for sorting a sequence of items, requiring ''O''(''n'') stack space, and the sort is stable. This requires ''n'' parallel processors. See {{section link|spaghetti sort#Analysis}}.<!-- see talk page discussion for June 2011 -->
|- align="center"
| [[Sorting network]]
| {{Sort|06|Varies}}
| {{Sort|06|Varies}}
| {{Sort|06|Varies}}
| {{Sort|21|Varies}}
| {{Varies}} (stable sorting networks require more comparisons)
| {{Yes}}
|align="left"| Order of comparisons are set in advance based on a fixed network size.
|- align="center"
| [[Bitonic sorter]]
| {{Sort|06|<math>\log^2 n</math> parallel}}
| {{Sort|06|<math>\log^2 n</math> parallel}}
| {{Sort|06|<math>n \log^2 n</math> non-parallel}}
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align="left"| An effective variation of Sorting networks. {{disputed inline|reason=I thought I heard that Batcher made odd-even merge sort to supersede bitonic.|date=June 2021}}
|- align="center"
| [[Bogosort]]
|style="background:#dfd"| {{Sort|15|{{mvar|n}}}}
|style="background:#fdd"| {{Sort|99|<math>(n\times n!)</math>}}
|style="background:#fdd"| {{Sort|99|Unbounded}} 
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align=left| Random shuffling. Used for example purposes only, as even the expected best-case runtime is awful.<ref name="Fun07">{{citation
 | last1 = Gruber
 | first1 = H.
 | last2 = Holzer
 | first2 = M.
 | last3 = Ruepp
 | first3 = O.
 | contribution = Sorting the slow way: an analysis of perversely awful randomized sorting algorithms
 | doi = 10.1007/978-3-540-72914-3_17
 | pages = 183–197
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007
 | date = 2007
 | url = http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | volume = 4475
 | isbn = 978-3-540-72913-6
 | access-date = 2020-06-27
 | archive-date = 2020-09-29
 | archive-url = https://web.archive.org/web/20200929161057/http://www.hermann-gruber.com/pdf/fun07-final.pdf
 | url-status = live
 }}.</ref>
Worst case is unbounded when using randomization, but a deterministic version guarantees <math>O(n\times n!)</math> worst case.
|- align="center"
| [[Stooge sort]]
|style="background:#fdd"| {{Sort|30|<math>n^{\log 3/\log 1.5}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\log 3/\log 1.5}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\log 3/\log 1.5}</math>}}
|style="background:#fdd"| {{Sort|15|{{mvar|n}}}}
| {{No}}
| {{Yes}}
|align="left"| Slower than most of the sorting algorithms (even naive ones) with a time complexity of {{math|1=''O''(''n''<sup>log 3 / log 1.5 </sup>) = ''O''(''n''<sup>2.7095...</sup>)}} Can be made stable, and is also a [[sorting network]].
|- align="center"
| [[Slowsort]]
|style="background:#fdd"| {{Sort|30|<math>n^{\Omega(\log n)}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\Omega(\log n)}</math>}}
|style="background:#fdd"| {{Sort|30|<math>n^{\Omega(\log n)}</math>}}
|style="background:#fdd"| {{Sort|15|{{mvar|n}}}}
| {{No}}
| {{Yes}}
|align="left"| A multiply and surrender algorithm, antonymous with [[divide-and-conquer algorithm]].
|- align="center"
| Franceschini's method<ref>{{Cite journal | doi = 10.1007/s00224-006-1311-1| title = Sorting Stably, in Place, with O(n log n) Comparisons and O(n) Moves| journal = Theory of Computing Systems| volume = 40| issue = 4| pages = 327–353
| date = June 2007| last1 = Franceschini | first1 = G. }}</ref>
|{{Sort|20|<math>-</math>}}
|style="background:#dfd"| {{Sort|20|<math>n\log n</math>}}
|style="background:#dfd"| {{Sort|20|<math>n\log n</math>}}
|style="background:#dfd"| {{Sort|00|1}}
| {{No}}
| {{Yes}}
|align="left"| Makes {{math|''O''(''n'')}} data moves in the worst case.  Possesses ideal comparison sort asymptotic bounds but is only of theoretical interest.
|}
Theoretical computer scientists have detailed other sorting algorithms that provide better than ''O''(''n'' log ''n'') time complexity assuming additional constraints, including:
* '''Thorup's algorithm''', a randomized algorithm for sorting keys from a domain of finite size, taking {{math|''O''(''n'' log log ''n'')}} time and ''O''(''n'') space.<ref>{{Cite journal |doi=10.1006/jagm.2002.1211 |title=Randomized Sorting in O(n log log n) Time and Linear Space Using Addition, Shift, and Bit-wise Boolean Operations |journal=Journal of Algorithms |volume=42 |issue=2 |pages=205–230 |date=February 2002 |last1=Thorup |first1=M. |s2cid=9700543 |author1-link = Mikkel Thorup}}</ref>
* A randomized [[integer sorting]] algorithm taking <math>O\left(n \sqrt{\log \log n}\right)</math> expected time and ''O''(''n'') space.<ref>{{Cite conference |doi=10.1109/SFCS.2002.1181890 |title=Integer sorting in O(n√(log log n)) expected time and linear space |conference=The 43rd Annual IEEE [[Symposium on Foundations of Computer Science]] |pages=135–144 |year=2002 |first1=Yijie |last1=Han |last2=Thorup |first2=M. |author2-link = Mikkel Thorup |isbn=0-7695-1822-2}}</ref>
* One of the authors of the previously mentioned algorithm{{who|date=March 2025}} also claims to have discovered an algorithm taking <math>O\left(n \sqrt{\log n}\right)</math> time and ''O''(''n'') space, sorting real numbers,<ref>{{Cite journal |last=Han |first=Yijie |date=2020-04-01 |title=Sorting Real Numbers in $$O\big (n\sqrt{\log n}\big )$$ Time and Linear Space |url=https://doi.org/10.1007/s00453-019-00626-0 |journal=Algorithmica |language=en |volume=82 |issue=4 |pages=966–978 |doi=10.1007/s00453-019-00626-0 |issn=1432-0541}}</ref> and further claims that, without any added assumptions on the input, it can be modified to achieve <math>O\left(n \log n / \sqrt{\log \log n}\right)</math> time and ''O''(''n'') space.<!--modification seems strictly worse?-->