Complexities of Basic Sorting Algorithms
Revision as of 12:22, 8 December 2013 by Arjun Suresh (talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Algorithm	Worst Case	Average Case	Best Case
Bubble	$\theta(n^{2})$	$\theta(n^{2})$	$\theta(n^{2})$
Selection	$\theta(n^{2})$	$\theta(n^{2})$	$\theta(n^{2})$
Insertion	$\theta(n^{2})$	$\theta(n^{2})$	$\theta(n)$ (when array is sorted)
Quick	$\theta(n^{2})$ (when array is sorted, and pivot taken from one end)	$\theta(nlgn)$	$\theta(nlgn)$
Merge	$\theta(nlgn)$	$\theta(nlgn)$	$\theta(nlgn)$
Heap	$\theta(nlgn)$	$\theta(nlgn)$	$\theta(nlgn)$