Comparison Sorting

A comparison algorithm determines relative ordering by comparing pairs of elements and swapping/reordering them if needed.

Parameters

$n$ : size of list

Related Problems

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 13 of 13 algorithms

				See more
Tim Sort	2002	$O(n \log n)$	$O(n)$
Intro Sort	1997	$O(n \log n)$	$O(\log n)$
Tree sort	1986	$O(n \log n)$	$O(n)$
Shell Sort (Sedgewick)	1986	$O(n^{1.33})$	$O(1)$
Shell Sort (Pratt)	1971	$O(n \log^2 n)$	$O(1)$
Heap Sort	1964	$O(n \log n)$	$O(1)$
Selection Sort	1962	$O(n^2)$	$O(1)$
Quick Sort	1961	$O(n^2)$	$O(\log n)$
Shell Sort (Frank & Lazarus)	1960	$O(n^{1.5})$	$O(1)$
Shell Sort (Shell)	1959	$O(n^2)$	$O(1)$
Bubble Sort	1956	$O(n^2)$	$O(1)$
Merge Sort	1945	$O(n \log n)$	$O(n)$
Insertion Sort	1940	$O(n^2)$	$O(1)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Insuffient Data to display table