Insertion-Sort Algorithm

Insertion-Sort algorithm is one of the simplest forms of algorithm used in computer science. In this article, we focus on using Insertion-Sort algorithm to sort an array in an ascending order. Basically, Insertion-Sort algorithm compares two numbers of an unsorted array or data set and swaps the smallest number/value with the largest number/value.

Let’s suppose we have an unsorted array arr which we want to sort in an ascending order.

arr[4] = {77, 33, 44, 11, 88}

In Insertion-Sort algorithm we always start from index one of the array. In this case, it means that 33 is our current element. Next, we compare the current element with all elements present on the left side of the current element. We continue this procedure until we traverse through the whole array or data set.

Now as mentioned before the value residing at index one is our current element and at index one, we have 33. On the left side of 33, we have 77.

Is 33 < 77 ?

Yes, 33 is smaller than 77. Hence, we swap the numbers. Now, the array looks like this,

Now, again we increment the current element. So, 44 is our current element. Next, we compare 44 with all elements present on the left side of 44. On the left side of 44, we have 77 and 33.

Is 44 < 77?

Yes, 44 is less than 77. Hence, we swap the numbers.

Is 44 < 33 ?

No, 44 is not less than 33. Hence, nothing will change. Now the array looks like this,

Again, we increment the index. Now at index 3, the residing element is our current element. In other words, 11 is our current element. Now, we compare the current element with all the elements present on the left side of the current element. On the left side of 11, we have 77, 44 and 33.

Is 11 < 77 ?

Yes, 11 is smaller than 44. Hence, we again swap the numbers.

Is 11 < 33 ?

Yes, 11 is smaller than 33. Hence, we again swap the numbers.

Now, the array looks like this,

Next, again we increment the index and now at index 4, the residing value is our current element. In this case, it is 88. As always, we compare the current element with all the elements present on the left side of the current element. On the left side of 88, we have 77, 44, 33 and 11.

Is 88 < 77 ?

No. Hence, nothing changes.

Is 88 < 44 ?

No. Hence, nothing changes.

Is 88 < 33 ?

No. Hence, nothing changes.

Is 88 < 11 ?

No. Hence, nothing changes.

So, the array will be,

Finally, we have successfully sorted an array in an ascending order by using Insertion-Sort algorithm.

Pseudocode for Insertion-Sort Algorithm (Ascending Order)

for j = 1 to length (arr) -1 do
    key <-- arr[j] // In the beginning our current element will                        
                   // be the value residing at index one

    i <-- j -1
    while i > 0 and arr[i] > key do
        arr[i+1] <-- arr[i]
        i <-- i-1
    arr[i+1] <-- key

Insertion-Sort algorithm is an in-place algorithm, meaning, it performs all computation in the original array and no other array is used. Hence, the space complexity is 0(1). It is also not that much effective for large data sets but can work good with data sets having less comparisons or are partially sorted.

Best Case Execution Time

If the data set is already sorted, then the Insertion-Sort algorithm takes n amount of time to check whether the array is already sorted or not. n is the number of elements present in the array / data set.

Average Case Execution Time

Average case execution time for Insertion-Sort algorithm is n².

Worst Case Execution Time

Worst case execution time for Insertion-Sort algorithm is also n².