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:
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!