# 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.

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

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

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

Now the first two elements in the list are sorted.

Next up we've got a 2.

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

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

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.

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

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

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

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

## 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.

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.

## What's next?

If you're ready to start applying these concepts to some problems, check out our mock coding interview questions.

They mimic a real interview by offering hints when you're stuck or you're missing an optimization.

. . .