Sorting

Description

A sorting algorithm is an algorithm that puts elements of a list in a certain order

Related Problems

Subproblem: Comparison Sorting, Non-Comparison Sorting

Related: Non-Comparison Sorting

Parameters

$n$: size of list

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Naive sorting	1940	$O(n^2)$	$O(1)$ (in-situ)	Exact	Deterministic
Selection Sort	1962	$O(n^2)$	$O(1)$ (in-situ)	Exact	Deterministic
Merge Sort	1945	$O(n\log n)$	$O(n)$	Exact	Deterministic
Bubble Sort	1956	$O(n^2)$	$O(1)$ (in-situ)	Exact	Deterministic
Intro Sort	1997	$O(n\log n)$	$O(logn)$	Exact	Deterministic	Time
Heap Sort	1964	$O(n\log n)$	$O(1)$ (in-situ)	Exact	Deterministic	Time
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
Tree sort	1986	$O(n\log n)$	$O(n)$	Exact	Deterministic	Time
Quick Sort	1961	$O(n^2)$	$O(\log n)$	Exact	Deterministic	Time & Space
Tim Sort	2002	$O(nlogn)$	$O(n)$	Exact	Deterministic
Cube Sort Parallel Implementation	1992	$O(nlogn)$	$O(n)$	Exact	Parallel	Time
Shell Sort (Shell)	1959	$O(n^2)$	$O(1)$	Exact	Deterministic	Time
Shell Sort (Frank & Lazarus)	1960	$O(n^{1.5})$	$O(1)$	Exact	Deterministic	Time
Shell Sort (Pratt)	1971	$O(n{\log }^{2}n)$	$O(1)$	Exact	Deterministic	Time
Shell Sort (Sedgewick)	1986	$O(n^{1.33})$	$O(1)$	Exact	Deterministic	Time
Bitonic Merge Sort Parallel Implementation	1968	$O({\log }^{2}n)$	$O(1)$	Exact	Parallel	Time
Thorup's Sorting Algorithm	2002	$O(n\log \log n)$	$O(n)$	Exact	Deterministic	Time & Space
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
Odd Even Sort Parallel Implementation	1972	$O(n^2)$	$O(1)$	Exact	Parallel	Time
Spaghetti Sort Parallel Implementation	1984	$O(n)$	$O(1)$ auxiliary? per processor?	Exact	Parallel	Time

Time Complexity Graph