Editing Sorting algorithm (section)

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