INSERTION SORT

 

 

Insertion sort is an efficient algorithm for sorting a small number of elements. Insertion sort works the same way as one would sort a bridge or gin rummy hand, i.e. starting with an empty left hand and the cards face down on the table. One card at a time is then removed from the table and inserted into the correct position in the left hand. To find the correct position for a card, it is compared with each of the cards already in the hand, from right to left. The pseudocode for insertion sort is presented in a procedure called INSERTION-SORT, which takes as a parameter an array A[1 . . n] containing a sequence of length n that is to be sorted. (In the code, the number n of elements in A is denoted by length[A].) The input numbers are sorted in place: the numbers are rearranged within the array A. The input array A contains the sorted output sequence when INSERTION-SORT is finished. 

INSERTION-SORT (A)

1  for j <- 2 to length[A]

2       do key <- A[j]

3         Insert A[j] into the sorted sequence A[1 . . j - 1].

4        i <- j - 1

5        while i > 0 and A[i] > key

6           do A[i + 1] <- A[i]

7              i <- i - 1

8        A[i + 1] <- key

Figure 1.1 shows how this algorithm works for A = {5, 2, 4, 6, 1, 3}. The index j indicates the "current card" being inserted into the hand. Array elements A[1.. j - 1] constitute the currently sorted hand, and elements A[j + 1 . . n] correspond to the pile of cards still on the table. The index j moves left to right through the array. At each iteration of the "outer" for loop, the element A[j] is picked out of the array (line 2). Then, starting in position j - 1, elements are successively moved one position to the right until the proper position for A[j] is found (lines 4-7), at which point it is inserted (line 8).

Figure 1.1 The operation of INSERTION-SORT on the array A = {5, 2, 4, 6, 1, 3}. The position of index j is indicated by a circle.

In order to analyze insertion sort the INSERTION-SORT procedure is presented with the time "cost" of each statement and the number of times each statement is executed. For each j = 2, 3, . . . , n, where n = length[A], tj is the number of times the while loop test in line 5 is executed for that value of j. It is assumed that comments are not executable statements, and as such they take no time. The running time of the algorithm is the sum of running times for each statement executed; a statement that takes ci steps to execute and is executed n times will contribute ci n to the total running time 3. To compute T(n), the running time of INSERTION-SORT, the products of the cost and times columns are summed.

 

The insertion sort algorithm involves:
  1. Start with the result as the first element of the input.

  2. Loop over the input until it is empty, "removing" the first remaining (leftmost) element.
  3. Compare the removed element against the current result, starting from the highest (rightmost) element, and working left towards the lowest element.

  4. If the removed input element is lower than the current result element, copy that value into the following element to make room for the new element below, and repeat with the next lowest result element.

  5. Otherwise, the new element is in the correct location; save it in the cell left by copying the last examined result up, and start again from (2) with the next input element.