Insertion Sort

Github code

Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Characteristics of Insertion Sort:

  • This algorithm is one of the simplest algorithm with simple implementation
  • Basically, Insertion sort is efficient for small data values
  • Insertion sort is adaptive in nature, i.e. it is appropriate for data sets which are already partially sorted.

Working of Insertion Sort algorithm:

Consider an example: arr[]: {12, 11, 13, 5, 6}

   12      11      13      5      6   

First Pass:

  • Initially, the first two elements of the array are compared in insertion sort.
   12      11      13      5      6   
  • Here, 12 is greater than 11 hence they are not in the ascending order and 12 is not at its correct position. Thus, swap 11 and 12.
  • So, for now 11 is stored in a sorted sub-array.
   11      12      13      5      6   

Second Pass:

  •  Now, move to the next two elements and compare them
   11      12      13      5      6   
  • Here, 13 is greater than 12, thus both elements seems to be in ascending order, hence, no swapping will occur. 12 also stored in a sorted sub-array along with 11

Third Pass:

  • Now, two elements are present in the sorted sub-array which are 11 and 12
  • Moving forward to the next two elements which are 13 and 5
   11      12      13      5      6   
  • Both 5 and 13 are not present at their correct place so swap them
   11      12      5      13      6   
  • After swapping, elements 12 and 5 are not sorted, thus swap again
   11      5      12      13      6   
  • Here, again 11 and 5 are not sorted, hence swap again
   5      11      12      13      6   
  • Here, 5 is at its correct position

Fourth Pass:

  • Now, the elements which are present in the sorted sub-array are 5, 11 and 12
  • Moving to the next two elements 13 and 6
   5      11      12      13      6   
  • Clearly, they are not sorted, thus perform swap between both
   5      11      12      6      13   
  • Now, 6 is smaller than 12, hence, swap again
   5      11      6      12      13   
  • Here, also swapping makes 11 and 6 unsorted hence, swap again
   5      6      11      12      13   
  • Finally, the array is completely sorted.

Illustrations:

insertion-sort

Pseudo Code

procedure insertionSort(A: list of sortable items)
   n = length(A)
   for i = 1 to n - 1 do
       j = i
       while j > 0 and A[j-1] > A[j] do
           swap(A[j], A[j-1])
           j = j - 1
       end while
   end for
end procedure

This algorithm sorts an array of items by repeatedly taking an element from the unsorted portion of the array and inserting it into its correct position in the sorted portion of the array.

  1. The procedure takes a single argument, ‘A’, which is a list of sortable items.
  2. The variable ‘n’ is assigned the length of the array A.
  3. The outer for loop starts at index ‘1’ and runs for ‘n-1’ iterations, where ‘n’ is the length of the array.
  4. The inner while loop starts at the current index i of the outer for loop and compares each element to its left neighbor. If an element is smaller than its left neighbor, the elements are swapped.
  5. The inner while loop continues to move an element to the left as long as it is smaller than the element to its left.
  6. Once the inner while loop is finished, the element at the current index is in its correct position in the sorted portion of the array.
  7. The outer for loop continues iterating through the array until all elements are in their correct positions and the array is fully sorted.

complexity Analysis:

  1. The time complexity of the recursive implementation of the insertion sort algorithm is the same as the iterative implementation, which is O(n^2). 
  2. The space complexity is O(n) due to the recursion stack.
Scroll to Top