k-th element; when this is frequently true (such as if the input array is already sorted or partly sorted), insertion sort is distinctly more efficient compared to selection sort. On average (assuming the rank of the (''k'' + 1)-st element rank is random), insertion sort will require comparing and shifting half of the previous k elements, meaning that insertion sort will perform about half as many comparisons as selection sort on average.

In the worst case for insertion sort (when the input array is reverse-sorted), insertion sort performs