Insertion Sort

April 21, 2019 2 minutes

Insertion Sort algorithm takes input, an unsorted array or any other sequential data-structure and sorts the same in-place, one element at a time. The idea is similar to how a player sorts the playing cards in hand.

It is not the most optimum algorithm and performs poorly for large data sets. The average case complexity is $O(n^2)$. Consider the following example:

InsertionSort

For the given input array: $\{10,8,11,3,5\}$, following steps are performed:

  1. Element at second position ($1^{st}$ index) is compared with the previous element and is swapped if required. Thus $\{10,8,11,3,5\}$ becomes $\{8,10,11,3,5\}$.
  2. After that, $11$ is compared with $10$ but as these two are in order, no swapping is performed.
  3. Next, $3$ is compared with $11$, $10$ and $8$ and is found to be less than all these. Hence these three elements will be shifted one place to the right and $3$ will be positioned at index $0$.
  4. In the next step, $5$ is compared with $11$, $10$ and $8$ and these are shifted to one place to the right making space for $5$ at index $1$.
  5. With the completion of above step, we have our array sorted in increasing order.

It can be easily observed that the worst case scenario happens when all of the elements are already sorted in reverse order.

Pseudo Code

  1. Initialize :
    • length : length of input array.
  2. For every element from index 1 to length:
    • set currentElement = element at index i.
    • For all the elements present at left of currentElement, which are greater than currentElement :
      • Shift the elements to one place towards right.
    • Finally, set the currentElement on the newly created spot after shifting elements to the right.

Java Implementation

     public int[] sort(int[] input) {
        int length = input.length;
        for (int startIndex = 1; startIndex < length; startIndex++) {
            int pivot = input[startIndex];
            int prevIndex = startIndex - 1;

            while (prevIndex >= 0 && input[prevIndex] > pivot) {
                //shift to right
                input[prevIndex + 1] = input[prevIndex];
                prevIndex--;
            }
            input[prevIndex + 1] = pivot;
        }
        return input;
    }

A working java example with test case can be found here.

comments powered by Disqus