# 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 array. If the input array 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 array into a sorted subsection of the array, one item at a time.

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

We'll break the the array 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 array 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 array

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

## Implementation

Let's code it up:

public static void insertionSort(int[] theArray) { // for each item in the input array for (int i = 0; i < theArray.length; i++) { // shift it to the left until it's in the right spot int index = i; while (index > 0 && theArray[index - 1] >= theArray[index]) { int tmp = theArray[index - 1]; theArray[index - 1] = theArray[index]; theArray[index] = tmp; index -= 1; } } }

## Time Complexity

### Worst Case

In the worst case, the input array 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 array 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 array 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 arrays, 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.

. . .