The Rambling Programmer

Insertion Sort

Data Structures & Algorithms

Insertion sort! Insertion sort!?! Argh, I hear you saying, ‘why learn a sorting algorithm that has a one of the worst run times of the sort algorithms computer scientists are aware of.’ Well, to start, if you know that to be true, you likely don’t need a blog post to teach you about insertion sort. That being said, it’s true. Insertion sort is rarely, if ever the optimal sorting solution, so why learn it? Because it is a fundamental concept, or better yet a fundamental pattern that we as builders of software are likely to see often. The more familiar we are with this pattern on a fundamental level, the more likely we are to recognize it in the wild, and perhaps realize that there is a more optimal solution. I discussed the relevance of these fundamental Computer Science patterns in my previous article, Why CS for Web Devs?

Without further ado, let’s get into it. To think of insertion sort, the most common comparison is sorting a hand of cards. Most people do this intuitively, take one card at a time, working either left-to-right or right-to-left and place it in position among the cards already sorted.

The concept is fairly simple, so how do we convey it in code? One more illustration might help here. The animation below illustrates the algorithm very clearly.

Starting from the left, the first element can be considered sorted already, there is nothing to compare it to. Moving on to the second item we look behind it, to the left, we shift elements to the right until we find the place it fits, place it, then move on to the third element. Pretty straightforward. Now that we have a pretty good mental picture of how insertion sort works, let’s write some code.

The first step in designing this algorithm is fairly straightforward. We need to step through each element in the array. We do this with a simple for loop. See the code snippet below. Note that the for loop used is not very Ruby-esque, this was done on purpose, to highlight the fact that we aren’t iterating over the whole array. Instead, we assume that the first element is sorted, because we have no elements to compare it to. So we start with the second element of the array, i = 1. We set the current_element to the element at the current index, so we can overwrite it when we shift elements to the right and for inserting it back into the array when we find where it belongs. Finally we set the second pointer, j, to the element left of current_element, which has already been sorted.

def insertion_sort(array)
  # start with second element in array,
  # consider first element already sorted
  for i in 1...array.length
    current_element = array[i]
    j = i-1
  end
end

Now to compare the current_element to the previous, already sorted elements in the array. We have all the information we need thanks to the previous step, the current_element and the pointer, j, which we will decrement until one of two things occurs, we reach the front of the array and place the current_element there because it is smaller than all the other sorted elements, or we find an element that is smaller than the current_element and stop, because the current_element has found its place in line. All the while we are sliding each previous element at index j to the right to make a gap for our current_element with, array[j+1] = array[j]. See the gif above, for a reminder.

def insertion_sort(array)
  # start with second element in array,
  # consider first element already sorted
  for i in 1...array.length
    current_element = array[i]
    j = i-1

    # compare current_element to the elements to it's left
    # swap elements until current_element is in correct place
    while j >= 0 && array[j] > current_element
      array[j+1] = array[j]
      j = j-1
    end

    # we exited the while loop, indicating we found slot for
    # our current_element and place it accordingly
    array[j+1] = current_element
  end  
end

Hopefully, that cleared up the insertion sort for you if you had trouble understanding it before. In conclusion, I’d like to point out several details, gotchas, etc… with our algorithm. This algorithm mutates the array input, that is, it sorts the array in place. This is the most space efficient method. We could, however, create a new blank array to copy the elements into as we worked through the array given to us, this would allow us to leave the original array alone, but would take up double the space. This concept is what’s known as an algorithm’s space complexity.

Secondly, without diving too deep into the mathematics of runtime complexity, let’s see if we can at least glean an idea of what the worst case runtime might be based on some hints in the algorithm. Assuming that the size of the array is n elements. We know that at a minimum, we have to step through each element based on the for loop ( actually n-1 elements, but the 1 is negligible, especially as the size of the array gets to be huge ). Great, so we know that the algorithm’s big O is at least O(n). But wait, there is a while loop embedded inside that for loop, that complicates things. Envision an array that is sorted in reverse order. In that case we would have to iterate the for loop through every element in the array, and then iterate the while loop backwards through every element of the array. Whenever you have a for loop or a while loop, inside of another loop, you have basically multiplied your complexity by another factor of n ( there are exceptions to this rule, although, they are fairly uncommon ). So now we can say that the complexity of our algorithm is O(n * n) == O(n²). This is really a complex topic for another post, or series of posts.

Thanks for reading along, I’m eager to read your input. Perhaps you can write a non mutating version of this algorithm, implement the algorithm in another language, or even create an insertion sort for another data type such as a linked list. Until next time here are a few links that dive a little bit deeper into some of the concepts we discussed.

Insertion Sort

Big O Notation

Big-O Algorithm Complexity Cheat Sheet

In-Place Algorithm

Insertion sort, sweet!

Posted by Scott almost 8 years ago