Understanding Insertion Sort in Ruby

There are lots of ways to sort data. Insertion sort is particularly interesting because it sorts the data in place and is pretty easy to understand. Of course, most of us just use the #sort method. But interviewers still love to ask questions about sorting algorithms and related topics like Big-O notation. In this post, you'll learn not only how insertion sort works but also how to implement it yourself in ruby.

Note: This is part 4 in a series looking at implementing various sorting algorithms with Ruby. Part 1 explored bubble sort, part 2 explored selection sort, and part 3 explored merge sort.

As we continue to explore different methodologies for sorting data, we turn to insertion sort. There are a number of reasons to like insertion sort! First, insertion sort is stable, which means that it does not change the relative order of elements with equal keys. It's also an in-place algorithm, meaning that it does not create a new array to store the sorted elements. Finally, insertion sort is a pretty simple algorithm to implement, as you'll soon see!

Why Care

It's difficult to avoid sounding like a broken record here, but as we've discussed in all of the previous posts, it's important to have an understanding of various mechanisms to sort data and what the trade-offs are with each of the various methods. For example, while insertion sort isn't very useful for large datasets (we'll explore this more below), it can be just fine and quite efficient for small datasets and those that are already close to being sorted. You'll learn why once we walk through the implementation. Sure, you'll often use built-in methods that your programming language of choice provides for sorting, but it just might pop up as an interview question as either a pair-program exercise or perhaps related to time complexity. Luckily, by the time we're done with this post, you will be able to both code an insertion sort and understand the time complexity with ease.

A Visual Representation

Before we get started coding, I highly recommend checking out the following video. It explains insertion sort utilizing a dance, and personally, I can't get enough of it! :)

Insertion sort visual example

Step-by-Step Walk-Through of the Code

Let's look at the code!

def insertion_sort(array)
    for i in 1...(array.length)  # Step 1
        j = i # Step 2
        while j > 0 # Step 3
            if array[j-1] > array[j] # Step 4
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            j = j - 1 # Step 5
    return array

Step 1:

We start with a for loop that sets variable i to 1 and continues to increment until i equals the length of our array.

Step 2:

We create another variable j and initialize it with a value of 1 (since that is what i is).

Step 3:

Next, we have a nested while loop that will continue as long as j is greater than zero. Since we start with j equal to 1, we know this will execute at least once.

Step 4:

The if... else block probably looks scary at first, but don't worry. It will make sense once we walk through it (and you can always revisit the dance YouTube example!).

For the if condition, we check whether [j-1] is greater than array[j]. Since j is currently 1, we would essentially be comparing array[0] with array[1]. This makes sense because we're comparing the first two elements of the array.

If the first element (array[0]) is larger than the next one (array[1]), then of course we need to swap, which is what happens within the if block. However, if the value in array[0] is less than the value in array[1], then great! We don't need to do anything because it's already sorted, so we simply hit the break in the else block.

Step 5:

From here, we decrement j. Now, we're back to the for loop, and i is now going to be 2. You can imagine how we'll be comparing array[1] with array[2] for the first iteration within the while loop, and then we'll actually go through the while loop again because our j started at 2 vs. 1.

Example with Real Data

Let's walk through this code using the following example array: [5,7,2,10,9,12]

In the first iteration, we'll be comparing 5 and 7. Since 5 < 7, we quickly break out of the if/else and move on.

In the next iteration, we compare 7 and 2. Now, these values will need to be swapped, so we'll have [5, 2, 7, 10, 9, 12]. Then, we'll swap the 2 again with the 5 to end up with [2, 5, 7, 10, 9, 12].

In the next iteration within the for loop, we'll compare 10 and 7 -- Yay! They're already in order.

Moving on, we compare 10 and 9 and find that we need to swap. Then, 7 is less than 9, so we won't have to perform any other swaps. We're now left with [2, 5, 7, 9, 10, 12].

The last iteration finds 12, which is greater than 10, so voila! We're done and sorted.

Performance Analysis

While some of the sorting algorithms we've looked at, namely bubble sort, are very rarely practiced in real life, insertion sort can be a reasonable solution. Imagine if our array was already sorted -- the insertion sort would run very quickly and efficiently. On the flip side, what happens if we need to sort an array that was in reverse order. That'd be a nightmare situation for insertion sort.

If the array is already sorted, the insertion sort code will run at O(n) since it will only have to loop through n times. If you want to bear this out, add a puts i at the top of the method and run the program passing in an already-sorted array.

If the array is reverse-sorted, the insertion sort code will run at O(n^2) You might be able to visualize this in your head. Since it will have to make consecutive swaps, it will hit the if condition for every single element. Yikes! Again, feel free to try this out by passing in a reverse-sorted array and create a counter variable that is printed out.

Although worst case is O(n^2) which, as you may recall, is the same for bubble sort and selection sort, insertion sort is usually preferable. This is because, as we've seen, the best case could be O(n), whereas the best case for selection sort is O(n^2). Insertion sort also has fewer swaps than bubble sort, so it wins this battle.

Wrap Up

I hope that this post has been helpful and that you feel confident about understanding the pros and cons of insertion sort, as well as how the algorithm functions. If you're still itching for more, I recommend checking out the wikipedia page for insertion sort.

What to do next:
  1. Try Honeybadger for FREE
    Honeybadger helps you find and fix errors before your users can even report them. Get set up in minutes and check monitoring off your to-do list.
    Start free trial
    Easy 5-minute setup — No credit card required
  2. Get the Honeybadger newsletter
    Each month we share news, best practices, and stories from the DevOps & monitoring community—exclusively for developers like you.
    author photo

    Julie Kent

    Julie is an engineer at Stitch Fix. In her free time, she likes reading, cooking, and walking her dog.

    More articles by Julie Kent
    Stop wasting time manually checking logs for errors!

    Try the only application health monitoring tool that allows you to track application errors, uptime, and cron jobs in one simple platform.

    • Know when critical errors occur, and which customers are affected.
    • Respond instantly when your systems go down.
    • Improve the health of your systems over time.
    • Fix problems before your customers can report them!

    As developers ourselves, we hated wasting time tracking down errors—so we built the system we always wanted.

    Honeybadger tracks everything you need and nothing you don't, creating one simple solution to keep your application running and error free so you can do what you do best—release new code. Try it free and see for yourself.

    Start free trial
    Simple 5-minute setup — No credit card required

    Learn more

    "We've looked at a lot of error management systems. Honeybadger is head and shoulders above the rest and somehow gets better with every new release."
    — Michael Smith, Cofounder & CTO of YvesBlue

    Honeybadger is trusted by top companies like:

    “Everyone is in love with Honeybadger ... the UI is spot on.”
    Molly Struve, Sr. Site Reliability Engineer, Netflix
    Start free trial
    Are you using Sentry, Rollbar, Bugsnag, or Airbrake for your monitoring? Honeybadger includes error tracking with a whole suite of amazing monitoring tools — all for probably less than you're paying now. Discover why so many companies are switching to Honeybadger here.
    Start free trial