Insertion Sort Algorithm

Quick reference

	Complexity
Worst case time
Best case time
Average case time
Space

Strengths:

Intuitive. Ever arranged your cards while playing poker or go-fish? Chances are, you used something like insertion sort.
Space efficient. Insertion sort can be done in-place, requiring additional space.
Fast on a sorted list. If the input list is already sorted, then insertion sort runs in time.

Weaknesses:

Slow. Insertion sort usually takes time—too slow to be used on super-big data sets.

How It Works

Insertion sort works by inserting elements from an unsorted list into a sorted subsection of the list, one item at a time.

Here's how it'd work on this list:

We'll break the the list into two chunks: a sorted portion and an unsorted portion.

[8, 3, 2, 7, 9, 1, 4] can be broken into a sorted portion [8] and an unsorted portion [3, 2, 7, 9, 1, 4].

(The 0th item is "sorted" to start.)

Now we add the next item, 3, to our sorted portion.

(3) is the first element in the unsorted portion [3, 2, 7, 9, 1, 4].

It goes before 8, so we need to swap them.

(3) is smaller than its left neighbor (8). Swapping them, we have [3, 8, 2, 7, 9, 1, 4]. The first two elements are sorted.

Now the first two elements in the list are sorted.

Next up we've got a 2.

(2) is the first element in the unsorted portion [2, 7, 9, 1, 4].

It goes before the 8, so we'll swap them.

(2) is smaller than its left neighbor (8). Swapping them, we have [3, 2, 8, 7, 9, 1, 4].

2 is also smaller than 3, so we need to swap those as well.

(2) is still smaller than its left neighbor (3). Swapping them, we have [2, 3, 8, 7, 9, 1, 4]. The first three elements are sorted.

At this point, the first three elements are sorted.

As you can see, the idea is to "swap" each new item to the left until it's in the right spot.

The next unsorted item is a 7. It'll need to be swapped with the 8.

Once that's done, we can compare 7 and 3. Since 7 is bigger, we don't need to swap them. So we're done moving the 7 down.

No additional swaps are needed. We have [2, 3, 7, 8, 9, 1, 4], and the first four elements are sorted.

Now we've got the first four elements in sorted order.

9 is next, and it's already in the right spot.

(9) does not need to move at all. We have [2, 3, 7, 8, 9, 1, 4], and the first five elements are sorted.

We'll have to swap a bunch of elements to get the 1 down to the start of the list

(1) moves leftward, trading places with (9) [2, 3, 7, 8, 1, 9, 4], (8) [2, 3, 7, 1, 8, 9, 4], (7) [2, 3, 1, 7, 8, 9, 4], (3) [2, 1, 3, 7, 8, 9, 4], and (2) [1, 2, 3, 7, 8, 9, 4]. Finally, we have [1, 2, 3, 7, 9, 8, 4], and the first 6 elements are sorted.

Finally, we'll swap the 4 over to the right spot.

(4) moves leftward, trading places with (9) [1, 2, 3, 7, 8, 4, 9], (8) [1, 2, 3, 7, 4, 8, 9], and (7) [1, 2, 3, 4, 7, 8, 9] until it's larger than its left neighbor (3). We're left with [1, 2, 3, 4, 7, 8, 9], which is sorted.

Implementation

Let's code it up:

def insertion_sort(the_list): # For each item in the input list for index in xrange(len(the_list)): # Shift it to the left until it's in the right spot while index > 0 and the_list[index - 1] >= the_list[index]: the_list[index], the_list[index - 1] =\ the_list[index - 1], the_list[index] index -= 1

Time Complexity

Worst Case

In the worst case, the input list is in descending order (reverse-sorted order). So each time we insert an element into the sorted portion, we'll need to swap it with each of the elements already in the sorted list to get it all the way to the start. That's 1 swap the first time, 2 swaps the second time, 3 swaps the third time, and so on, up to n - 1 swaps for the last item.

Adding them all up:

1 + 2 + 3 + \ldots + (n - 2) + (n - 1)

That's the triangular series, whose sum is . Each swap costs constant time, so that's time overall.

Best Case

In the best case, the input list is already sorted. We'll still need to compare every element to the one before it, to check if it needs to be swapped. But the answer will always be "no." So we sidestep the swapping entirely and just do those comparisons, costing time overall.

Space Complexity

Insertion sort doesn't rely on any extra lists, so it's space.

Interview coming up?

Get the free 7-day email crash course. You'll learn how to think algorithmically, so you can break down tricky coding interview questions.

No prior computer science training necessary—we'll get you up to speed quickly, skipping all the overly academic stuff.

No spam. One-click unsubscribe whenever.

You're in! Head over to your email inbox right now to read day one!