Datastructures/Sorting Algorithms

Sorting Algorithms

Summary of Sorting Algorithms
Algorithm	Worst CT	Avg. CT	Best CT	Stable	In-place	Online	Inventor
Insertion sort	$O (n 2)$	$0.25 * W C T$	$O (n)$	Y	Y	Y	?
Merge sort	$O(n\,\lg n)$	$O(n\,\lg n)$	$?$	Y	N	Maybe	John Von Neumann
Heapsort	$O(n\,\lg n)$	$O(n\,\lg n)$	$O(n\,\lg n)$	N	Y	N	?
Quicksort	$O (n 2)$	$1.39 * B C T$	$O(n\,\lg n)$	N	Maybe	?	C.A.R. (Tony) Hoare

Advantages: stable, in-place, O(n) on sorted lists, very simple: fast for very small lists ( $n < 10$ ). Good locality-of-reference.

Advantages: stable, good locality-of-references, parallelizes well, can be modified for online sorting, good choice for sorting linked lists.

Disadvantages: not in-place, quite complex to implement

Advantages: in-place, parallelizes poorly, quite simple to implement.

Disadvantages: not stable, poor locality-of-reference, not online.

Advantages: Can be implemented as in-place, often fast in practice, parallelizes well.

Disadvantage: not stable, poor worst-case performance with common worst-case, performance dependent on pivot choice.