Insertion Sort on Nearly-Sorted Arrays

Insertion sort is adaptive: it runs in $\Theta(n)$ on nearly-sorted input where merge/quicksort still pay $\Theta(n\log n)$.