Comparison sorting

Overview

Compares insertion sort, merge sort and quicksort and explains the n log n lower bound.

Insertion sort is quadratic in the worst case but fast on nearly sorted input. Merge sort is always n log n but uses extra memory. Quicksort is n log n on average and in place, but quadratic on bad pivots.

Any sort that only compares pairs of elements needs at least on the order of n log n comparisons, because it must distinguish n factorial possible orderings.