Sorting Algorithms: Insertion Sort
Sorting Algorithms: Insertion Sort
Oh no, the stuffed animals are fighting again. They seem to think that they're ordered by how much you like them. (They are, but don't tell them that.) You need to re-order them before one of them starts losing stuffing.
Stuffed animals are tough to sort, but don't worry: we've got you covered. Let's look at a sorting algorithm where you sort items as you insert things into a list. We're going to cleverly name this sort "Insertion Sort."
This sort's super common for people working with small sets of data, so it's perfect for your collection of five stuffed animals. It all begins with a set of objects and an empty list where we insert elements as where they belong as we go.
![A list with indices 0 – 4, with the names, Ms. Andry, Anita Cardigan, Old Man Higgins, Snuggles Pettinger, III, and Mr. Brightside.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms9.png)
(The first row tells us the index—where it lives in the list—of each stuffed animal.)
You'd create an empty space in front of you like so:
![An empty list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms10.png)
You then take the first element and put it in the first place in the empty list.
![Ms. Andry is grayed out, and entered in the first box of the empty list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms11.png)
It's in a list of one, so of course it's sorted. Now you move on to the next stuffed animal and compare it with the first. Since the name Anita Cardigan comes alphabetically before Ms. Andry, move Ms. Andry to the right.
![Anita Cardigan is grayed out too, and placed in front of Ms. Andry in the new list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms12.png)
We've reached Old Man Higgins. We compare him to the last item, Ms. Andry, and find he comes alphabetically after her, so we put him at the end of the list.
![Old Man Higgins is also grayed out and added to the end of the new list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms13.png)
Snuggles Pettinger, III, when compared to Old Man Higgins, comes alphabetically after Higgins, so he's placed in the next empty space.
![Snuggles is grayed out and added to the end of the new list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms14.png)
Now we've reached the end of the list with Mr. Brightside. Alphabetically, he comes before Snuggles, so we compare him to Old Man Higgens.
Again, Mr. Brightside comes before, so we compare him with Ms. Andry to find that he also comes before her. After comparing him to Anita Cardigan, though, we find that Mr. Brightside has finally found his rightful place between Anita and Ms. Andry.
![The entire list is grayed out.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms15.png)
Alternative Implementation
You might want to sit down before we tell you a secret. We can actually do this same sort without the extra list.
Mind. Blown.
If we start by calling the List index zero a sorted list—since it only has one element—we can then go to the next index, pull the element out of the list, like so:
![Anita Cardigan is separated from index 1, with Ms. Andry as the only element in the](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms16.png)
Once we find that Anita comes before Ms. Andry, we can shift Ms. Andry to where Anita was,
![Ms. Andry was moved to index 1 of the now two-element sorted piece of the list so that Anita Caridgan can be placed at index 0.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms17.png)
place Anita in the now empty space at index zero,
![Now the floating square is empty.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms18.png)
and call this section of the list as sorted. With Old Man Higgins, one comparison with Ms. Andry and he's already sorted, so we don't even need to pull him out. Thank goodness. Higgins has bad knees; we were a little worried they might give out if we moved him too much.
![Now Old Man Higgins is counted in the sorted list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms19.png)
Snuggles doesn't need to move either.
![Snuggles is now a part of the sorted list without needing to move.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms20.png)
Now the fun starts with Mr. Brightside, the eternal optimist. Since we've compared him with Snuggles and found that Mr. Brightside should come first, we take him out and find that he also comes before Old Man Higgins.
![Mr. Brightside's in the floating square above the list.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms21.png)
And before Ms. Andry (despite her protests about being pushed aside by a man).
![Now Mr. Brightside's above the index with Ms. Andry (1).](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms22.png
)
Until he's compared to Anita, who comes before him alphabetically. Every stuffed animal except Anita shifts to the right to make room for Mr. Brightside.
![Mr. Brightside is now above an empty index 1 with all the following elements moved one index over.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms23.png)
Then we insert Mr. Brightside and we're done.
![Now the list is sorted.](https://media1.shmoop.com/shmooc/ap-computer-science/SortingAlgorithms_imagesPart1/SortingAlgorithms24.png)
The pseudocode for this algorithm looks something like this:
DEFINITION InsertionSort(List L) LET N be the length of L FOR i in range 0 to N: LET j equal i WHILE j > 0 and L[j – 1] > L[j]: SWAP L[j] and L[j – 1] j = j – 1 END while END for
In the worst case, this algorithm runs in O(n2) time, but for small amounts of data, it's actually faster than "more efficient" algorithms.
By small, we mean Ten Items or Less checkout lane small. Please don't try to sort your entire Pokémon collection using Insertion Sort.
Bonus: It doesn't take much memory to use.