Insertion Sort

In this section, we consider an application of the decrease-by-one technique to sorting an array A[0..n − 1]. Following the technique’s idea, we assume that the smaller problem of sorting the array A[0..n − 2] has already been solved to give us a sorted array of size n − 1: A[0] ≤ … ≤ A[n − 2]. How can we take advantage of this solution to the smaller problem to get a solution to the original problem by taking into account the element A[n − 1]? Obviously, all we need is to find an appropriate position for A[n − 1] among the sorted elements and insert it there. This is usually done by scanning the sorted subarray from right to left until the first element smaller than or equal to A[n − 1] is encountered to insert A[n − 1] right after that element. The resulting algorithm is called straight insertion sort or simply insertion sort.

Though insertion sort is clearly based on a recursive idea, it is more efficient to implement this algorithm bottom up, i.e., iteratively. As shown in Figure 1, starting with A[1] and ending with A[n − 1], A[i]is inserted in its appropriate place among the first i elements of the array that have been already sorted (but, unlike selection sort, are generally not in their final positions).

Here is pseudocode of this algorithm.

The operation of the algorithm is illustrated in Figure 4.4.
The basic operation of the algorithm is the key comparison A[j ]> v. (Why not j ≥ 0? Because it is almost certainly faster than the former in an actual computer implementation.

The number of key comparisons in this algorithm obviously depends on the
nature of the input. In the worst case, A[j ] > v is executed the largest number of times, i.e., for every j = i − 1,…, 0. Since v = A[i], it happens if and only if A[j ] > A[i] for j = i − 1,…, 0. (Note that we are using the fact that on the ith iteration of insertion sort all the elements preceding A[i] are the first i elements in the input, albeit in the sorted order.) Thus, for the worst-case input, we get A[0]>A[1] (for i = 1), A[1] > A[2] (for i = 2),…,A[n − 2] > A[n − 1] (for i = n − 1). In other words, the worst-case input is an array of strictly decreasing values. The number of key comparisons for such an input is

Thus, in the worst case, insertion sort makes exactly the same number of comparisons as selection sort.

In the best case, the comparison A[j ] > v is executed only once on every
iteration of the outer loop. It happens if and only if A[i − 1] ≤ A[i] for every
i = 1,…,n − 1, i.e., if the input array is already sorted in non decreasing order.
Thus, for sorted arrays, the number of key comparisons is

This very good performance in the best case of sorted arrays is not very useful by itself, because we cannot expect such convenient inputs. However, almost-sorted files do arise in a variety of applications, and insertion sort preserves its excellent performance on such inputs.

A rigorous analysis of the algorithm’s average-case efficiency is based on
investigating the number of element pairs that are out of order It shows that on randomly ordered arrays, insertion sort makes on average half as many comparisons as on decreasing arrays, i.e.,

This twice-as-fast average-case performance coupled with an excellent efficiency on almost-sorted arrays makes insertion sort stand out among its principal competitors among elementary sorting algorithms, selection sort and bubble sort.