Sorting Algorithms: Insertion Sort

Let’s Sort! In this series, I’ll be covering sorting algorithms. Most programming languages will come with a built-in sort function but in order to write better code, you need to know what’s going on in the background. If you are preparing for software engineering interviews, it’s very likely that one or more sorting algorithms may come up during your interviews. The sorting algorithms I’ll be covering in this series are:

1. Bubble Sort
2. Insertion Sort
3. Selection Sort
4. Merge Sort
5. Quick Sort
6. Radix/Bucket Sort
7. Heap Sort

What is Insertion Sort?

Insertion sort does not score high on performance but it is a simple sorting algorithm to understand and implement.

How Does it Work?

Let’s have a look at the array we want to sort:

The way we are going to sort this list is to look at the first value in the array and consider it sorted (tentatively). The first element is in our array is 6, so we consider 6 as sorted and everything to the right of 6 as unsorted.

Then we have a look at the rest of the array to the right of 6. We are going to iterate through each value and insert it into our “sorted” array.

In the diagram below, blue is “sorted” and red is our current value we are working with:

We look at our current value = 3 and we look at the sorted part. Where does 3 go in the sorted part? It goes before 6 so lets swap them:

So far so good! Our next current value is 9. Is 9 less than 6? No, it isn’t so 9 is in its correct position.

Ok. Current = 8. Is 8 less than 9? Yup. Let’s swap:

Current = 4. Is 4 less than 9? Swap:

4 is still red because it hasn’t completed being sorted. Is 4 less than 8? less than 6? We don’t stop working with 4 until everything to its left is less than or equal to it:

Current = 6:

Current = 5:

Current = 2:

And we are done!

Time and Space Complexity

You can see from the diagrams how many steps it takes to get an array sorted with Insertion Sort. But just how long?

If we have n values in our array, Insertion Sort has a time complexity of O(n²) in the worst case. In the best case, we already have a sorted array but we need to go through the array at least once to be sure! Therefore in the best case, Insertion Sort takes O(n) time complexity.

What about space complexity? Insertion Sort sorts in-place, meaning we do not need to allocate any memory for the sort to occur. Space complexity is O(1).

Code Implementation

Let’s look at Insertion Sort in Python:

We define our insertionSort function and it takes in an array of integers. Now we need to start iterating through our array. Remember we chose current to start at index 1 because the first element in our array was marked as sorted. Our for loop will therefore start from index 1:

def insertionSort(array):
    for i in range(1, len(array)):

Now we need to look backwards. To do that, we need another loop. We will add in a while loop using an iterator called j. j will equal toi at the start and will move back in the array until just before the first element. Why just before? When we compare, we will be comparing array[j] with array[j — 1] so we dont want to accidentally check array[-1] if j = 0!

If array[j] is less than the element before it at array[j — 1], we swap them. We then decrement j to move on to the next comparison. Our while loop will stop if j = 0 or we find an element that is greater than the current element.

def insertionSort(array):
    for i in range(1, len(array)):
        j = i
        while j > 0 and array[j] < array[j - 1]:
            array[j], array[j - 1] = array[j - 1], array[j]
            j -= 1
    return array

And that is Insertion Sort. It’s simple. It’s slow. But it’s important to learn and hopefully, it will help you understand why some sorting algorithms are more optimal than others.

Thanks for reading!

References

Insertion Sort - GeeksforGeeks