Sorting

Input: Unordered collection of size n
Output: Ordered collection of size n
Properties
- Stable sort: the order between equal elements remains after sorting

Basic Sorts

Case	Selection	Bubble	Insertion
Worst	$O (n^{2})$	$O (n^{2})$ (reversed)	$O (n^{2})$ (reversed)
Average	$O (n^{2})$	$O (n^{2})$	$O (n^{2})$
Best	$O (n^{2})$	$O (n)$ (already sorted)	$O (n)$ (already sorted)
Space	$O (1)$	$O (1)$	$O (1)$

Case	Shell	Merge	Quick
Worst	$O (n^{2})$	$O (n lo g n)$	$O (n^{2})$ (bad pivots chosen)
Average	$O (n^{5/4})$	$O (n lo g n)$	$O (n lo g n)$
Best	$O (n^{7/6})$	$O (n lo g n)$	$O (n lo g n)$
Space	$O (1)$	$O (n)$	$O (lo g n)$ (from recursion stack)

Theorem

Any deterministic compare-based sorting algorithm must make $Ω (n lo g n)$ compares in the worst case

Proof:

2^{h} h \leq n! \leq lo g_{2} (n!) \leq n lo g_{2} (n) - \frac{n}{ln 2} □