3.2. Insertion Sort

Insertion sort is a sorting algorithm that works the way we sort playing cards in our hands.

The algorithm works by maintaining two sublists in a given array:

1. The sublist which is already sorted.

2. Remaining sublist which is unsorted.

The algorithm iteratively “inserts” the next element from the unsorted sublist into the correct position in the sorted sublist. This process continues until the unsorted sublist is empty.

Similar to selection sort, the algorithm does not require any extra space the two sublists are maintained by a single variables tracking the first element of the unsorted sublist. Everything before this variable is sorted and everything after it is unsorted.

Fig. 3.4 Insertion Sort is similar to how we sort playing cards in our hands. We iteratively insert the next element from the unsorted sublist into the correct position in the sorted sublist.

3.2.1. Steps

The algorithm works as follows:

1. Initialize a iterator \(i\) to \(1\).

2. Call the element at \(i^{th}\) location \(key\) i.e. \(key \leftarrow L[i]\).

3. Iterate over sublist to the left of \(i\) from right to left i.e. iterate over the list from \(i-1\) to \(0\) using an iterator called \(j\). The sublist from \(i-1\) to \(0\) is the sorted sublist.

4. For all values \(L[j] > key\), shift them one place to the right i.e. set \(L[j+1]\) to \(L[j]\) until \(L[j] > key\).

5. Once you find a value \(L[j] \leq key\), you’ve found the correct location of \(key\). Set \(L[j+1]\) to \(key\).

6. Increment \(i\) by \(1\) and repeat steps 2-5 until \(i\) is equal to \(n-1\).

Fig. 3.5 Insertion Sort is similar to how we sort playing cards in our hands. We iteratively insert the next element from the unsorted sublist into the correct position in the sorted sublist. Note that the animation above is sorting in descending order.

3.2.2. Psuedocode

Algorithm 3.2 (Insertion Sort Algorithm)

Inputs Given a list of numbers \(L\) of length \(n\)

Output A sorted list of numbers \(L\) of length \(n\)

\(n\) \(\leftarrow\) length(L)

For \(i\) from \(1\) to \(n-1\):
  \(key\) \(\leftarrow\) \(L[i]\)
  \(j\) \(\leftarrow\) \(i-1\)
  While \(j \geq 0\) and \(L[j] > key\):
      \(L[j+1]\) \(\leftarrow\) \(L[j]\)
      \(j\) \(\leftarrow\) \(j-1\)
  end While
  \(L[j+1]\) \(\leftarrow\) \(key\)
end For

3.2.3. Analysis

The time complexity of insertion sort depends on the initial order of the elements in the input array.

In the worst case, the array is sorted in reverse order. In this case, the algorithm will perform \(n\) comparisons and \(n(n-1)/2\) swaps. Thus, the time complexity is \(O(n^2)\).

In the average case, the array is randomly ordered. In this case, the algorithm will perform \(n\) comparisons and \(n(n-1)/4\) swaps. Thus, the time complexity is \(O(n^2)\).

In the best case, the array is already sorted. In this case, the algorithm will perform \(n\) comparisons and \(0\) swaps. Thus, the time complexity is \(O(n)\). Note that the best case of insertion sort is better than the best case of selection sort.

The space complexity of insertion sort is \(O(1)\) in all cases as the algorithm does not require any extra space.

3.2.4. Comparison with Selection Sort

Selection and Insertion sort are similar algorithms with some subtle but key differences.

3.2.4.1. Similarities

They are similar in that they are

• Both decrease and conquer sorting algorithms

• Both maintain two sublists in a given array:

  • The sublist which is already sorted.

  • Remaining sublist which is unsorted.

• Both have a time complexity of \(O(n^2)\)

• Both are in-place sorting algorithms

• The space complexity of both is \(O(1)\)

3.2.4.2. Differences

They two key difference in that:

1. In selection sort, most of the work done is in “selecting” (finding) the smallest element in the unsorted sublist.

   
   

   In insertion sort, most of the work is done in “inserting” the next element from the unsorted sublist into the correct position in the sorted sublist.

Fig. 3.6 The key difference between Selection Sort and Insertion Sort is that most of the work done in Selection Sort is in tge “Select” (finding) step and most of the work done in Insertion Sort is in the “Insert” step.

2. Depending on the implementation and the data, insertion sort can, in the best case, be faster than selection sort.