Non-Comparison Sorting (Sorting)

From Algorithm Wiki
Jump to navigation Jump to search


A sorting algorithm is an algorithm that puts elements of a list in a certain order, not using comparisons between elements (so elements are typically integers or real numbers).

Related Problems

Generalizations: Sorting

Related: Comparison Sorting


$n$: size of list

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Counting Sort 1954 $O(n+k)$ $O(n+k)$ Exact Deterministic Time
Bucket Sort 1940 $O( n² )$ $O(n)$ Exact Deterministic
Radix Sort 1940 $O(wn)$ $O(w+n)$ Exact Deterministic
Naive sorting 1940 $O(n^{2})$ $O({1})$ Exact Deterministic
Flash Sort 1998 $O(n^{2})$ $O(n)$ Exact Deterministic Time & Space
Bead Sort 2002 $O(n)$ $O(n^{2})$ Exact Deterministic Time
Burst Sort 2004 $O(wn)$ $O(wn)$ Exact Deterministic Time
Spreadsort 2002 $O(n \log n)$ $O(n)$? Exact Deterministic Time
Spaghetti Sort Parallel Implementation 1984 $O(n)$ $O({1})$ auxiliary? per processor? Exact Parallel Time

Time Complexity Graph

Sorting - Non-Comparison Sorting - Time.png