A Simple Insertion Sort

Again, there are many examples on the web which make you to follow a lot of indices and nested loops which makes insertion sort look difficult. The intent of this post is to help you understand the concept behind insertion sort and code in few minutes.

Insert an element into the sorted array
The key to understand insertion sort is to first write a simple function that would insert an element into a given array that is already sorted. There are a couple of assumptions we are going to make here, to make the job easy.

1. Assume that the array has space to insert one more element i.e there is an additional empty space at the end of the array (There is no need to resize the array to add space for the new element)
2. The elements in the array are already sorted, so we need to insert the new element in the right place or index of the array.

Here is how we do it

1. Pick the last element in the array i.e the element before the empty slot.
2. Compare the above array element with the new element we want to insert.
3. If the array element is larger than the new element - We  move the array element to a higher memory address or array index.
4. We repeat the above process till we hit a condition where the new element is larger than array element.
5. In this case we insert the new element in the current index/free slot of the array.

Here is the diagram that shows the step by step movement of the free slot

1. Step 1 :  Free slot is at the end of the array, we pick the last but one element in the array which is 10, since 10 is larger than 4, we move 10 to next higher index, now free slot is one level below the last element.
2. Step 2 :  Now we pick the next element which is 7, since 7 is larger than 4, we move 7 to next higher index, now free slot is two levels below the last element.
3. Step 3 :  Now we pick the next element which is 6, since 6 is larger than 4, we move 6 to next higher index, now free slot is three levels below the last element.
4. Step 4 :  Now we pick the next element which is 3, since 3 is less than 4, we insert 4 in the current index.

Here is a simple code to do it.

void sampleInsert(int array[], int value) {

        // Assuming last item is empty
        int reverseIndex = array.length - 1;

        //start the loop from second last element since last is empty
        for (int i = array.length - 2; i >= 0; i--) {

            //If the array element is greater than the value
            //move the array element to the next higher index
            if (array[i] >= value) {
                array[i + 1] = array[i];
                reverseIndex = i;
            } else {
                break;
            }
        }

        array[reverseIndex] = value;
    }

Now that we have understood the insert routine/method, lets look at insertion sort algorithm itself.

Insertion Sort algorithm
Here is how insertion sort is often explained, it works the way you might sort a hand of playing cards

1. We start with an empty sorted array ( this means our array is full of unsorted elements )
2. Then remove one element at a time from the unsorted array, and insert it into the correct position in the sorted array.
3. To find the correct position for the element, we use the above sample code.

Code
Now lets try to code implement insertion sort algorithm in the simplest possible way as explained above.

public void sort(int array[]) {

        //Ignore the first array element [0] since array with one element is always sorted
        //start from the array [1] -- Get that element and insert
        for (int index = 1; index < array.length; index++) {
            insert(array, index);
        }
    }
    

Done, that's it. All we are doing in the above code is take/read each element in the unsorted array and inserting that element back into the array which does the sort.

As you can see the algorithm can be implemented in few lines, easy to remember once you know how to implement insert routine.

Here is the the insert routine/method, same code as above sampleInsert() - The difference is, rather than taking a value to insert, it takes the index of value to insert.

void insert(int array[], int currentIndex) {

        //value of the element to be inserted
        int value = array[currentIndex];

        //iterate in the loop for all elements below the currentIndex
        int reverseIndex = currentIndex;
        for (int i = currentIndex - 1; i >= 0; i--) {

            //If the array element is  greater than the value
            //move the array element to the next higher index
            if (array[i] >= value) {
                array[i + 1] = array[i];
                reverseIndex = i;
            } else {
                break;
            }
        }
        array[reverseIndex] = value;
    }

What is the complexity of the above algorithm ?  
Average and Worst Case:
Its O(n²) - Since there is a nested loop. 

Why ?
There is loop in the above sort() method, which calls insert(), which again has a loop. Hence a nested loop.  

Best case : 
Now lets consider the best case. What if the array is already sorted and we do a insertion sort on this ?. This means we need to insert element only at the end of the array. So the inner for loop never gets executed. So best case is O(n).

Space Complexity is none since we did not allot any new arrays.

Check the other article on How to find the complexity of a code and rest of the articles here.

Source code
Here is the complete insertion sort sample java file used in this post.