Gotta Sort ’em All! (Part 1)
An Introduction to Sorting Algorithms and Time Complexity with Pokemon
9:00 am, In a meeting room at Silph Co. Headquarters, Saffron City
“Welcome, Ash. My name is Professor Cypress, software team lead of Silph. I must say your resume is very impressive. In my 10 years here, I can count on one hand the number of times someone had ‘Indigo League Champion’ in their achievements section. And oooh, you were given a medal by this very company, for meritorious service beyond the call of duty? And to top it all of, a personal letter of reference from my friend Professor Oak? Very impressive, I must say.”
“Thank you, sir”, Ash replied.
“However, you will still need to pass our final challenge.” He gestured at the PokeBalls on the shelf. “As you know, every class of Pokemon on that shelf has an ID number in the National Pokedex. Your challenge is to sort all the Pokemon from smallest to largest.”
The Bubble Sort
One of the simplest methods of sorting is the bubble sort, which revolves around comparing items to their neighbours and swapping them if they are out of order. Let’s start with an example where we sort the following 12 Pokemon in Pokedex (numerical) order:
In this example, we would begin by comparing the first two items — 015 indeed comes before 145, so we’re fine. Then we compare 146 to 016 — this time the items are out of order, so we swap them.
Then we’ll compare 145 to 149, which results in no change. Next, 149 is larger than 130, so we have to do a swap.
After a few more swaps, we eventually end up with 149 (Dragonite) at the end of the list where it belongs. Note that we needed to compare 11 pairs of Pokemon before correctly deciding that Dragonite comes last on the list.
Then we’ll go back to the left side of the list and try again. The first three items are in order, but after that, we need to swap 130 and 145. And this time, 145 (Zapdos) will “bubble” all the way to the second-last item on the list. We needed to compare 10 pairs of Pokemon to place Zapdos in its right place.
If we continue this process, we will make a total of 11 + 10 + 9 + … + 1 = 66 comparisons, to arrive at our sorted list:
This isn’t too bad, if we could do one comparison and/or swap a second, the whole sorting process would only take a minute.
While this seems simple enough, it quickly becomes impractical when you have longer lists to sort. Imagine if you had to sort all 151 Kanto Pokemon. Not only do you now need to do 150 comparisons just to sort one Pokemon into the right place, you’d now need to pass through the entire list 150 times, for a total of 150 + 149 + …. + 1 = 11,325 comparisons. Now, a one-minute sort has become three hours.
When your list is twice as long, it takes four times as long to complete the bubble sort. In computer science speak, we say that the bubble sort has a time complexity of O(N²) — it’s proportional to the square of the number of items you have.
The Insertion Sort
Ah, but what if, instead of just swapping items in place, we made a new list and started populating it one by one with the items in order?
We begin by putting 015 (Beedrill) into the new list.
The next item in our original list is 145, which comes after 015, so we place it to the right.
The next item in our original list is 016 (Pidgey). This is larger than 015, but smaller than 145, so we place it in the middle. Notice that we had to do two comparisons to find a spot for Pidgey.
Next we have 149 (Dragonite), which is bigger than all three items in the new list. So we place it at the right-most end. Notice that we had to do three comparisons to find a spot for Dragonite.
Next up is 130 (Gyarados). It is bigger than the first two items, but smaller than the third, so we place it between the second and third Pokemon in the new list. This time, we had to do 3 comparisons to find the right spot for Gyarados.
I don’t want to bore you with the details (so just trust me on this), but if you go down the rest of the list, you would have to do a total of 42 comparisons to complete the sort.¹
This is a little bit better than the bubble sort, because although we still have to pass (or iterate) through the list 11 times, sometimes we’ll get lucky and the Pokemon belongs close to the beginning of the list, and we don’t have to do any more comparisons after that.
But once you start scaling up, the insertion sort doesn’t fare too well. If you double the list length, you have to iterate through the list twice as many times, and each time you iterate through, you’ll need to make twice as many comparisons before finding the right spot. Doubling the list on an insertion sort still means you have to make four times as many comparisons. In other words, the insertion sort, like the bubble sort, has a time complexity of O(N²).
The Quicksort
The quicksort works by picking a single item out of the list to be a pivot. After this, we arrange all the other items either to the left or right of the pivot. Once again, to recap our example:
Now, say we choose the 069 Bellsprout as a pivot, then all the Pokemon with numbers below 069 are moved to the left half, and everything above 069 to the right half, but we keep them in the same order otherwise. After the first step:
Step 2: Next, we choose a pivot in both the left and right halves of the list (let’s say we choose 039 — Jigglypuff and 130 — Gyarados), and move items to the left or right of those pivots. (In other words, this algorithm runs recursively). As it turns out, the first time we got lucky with our choice of pivot and we managed to split the list into two roughly equal halves, but in this second step we won’t be so lucky:
On the left side, it turns out 039 is higher than all the other items, so everything gets moved to the left of 039.
And on the right side, it turns out 130 is lower than all the other items in that half, so everything gets moved to the right of 130.
Ouch! This time we got very unlucky. Now we still have a sub-list of 5 items on the left to sort, and a sub-list of 4 items on the right.
If we continue the process, each time taking the middle element of each sub-list as a pivot, we would get the following for Steps 3, 4, and 5:
And voila, a sorted list! With the quicksort, we only needed to make 5 passes through the list. If you break it down, in each step, P, the number of pivot items, roughly doubles, and the number of comparisons we need to make is N-P.
In this particular case, measuring by the number of comparisons, quicksort is slightly faster than the insertion sort.
However, once you start scaling up, the story changes. If we had a list of 24 Pokemon to quicksort, for example, our first step would be to pick a pivot item to move everything to the left and right of — and after that step we’d end up with two sub-lists of roughly 12 Pokemon each. When you double your list size, you only have to do one more quicksort step.
If you quadruple the list size, you only have to do two more steps.
Eight times the list size? Three more steps.
You’ll notice we’re going up by powers of two here.
So to bring back the earlier example where you have to sort a list of 151 Pokemon, the quicksort would look something like:
To be fair, this is an ideal scenario, where we never have an “unlucky” pivot choice. But when you have a much longer list, it’s a lot more unlikely you’ll just happen to pick the largest or smallest number as a pivot — what are the chances? Most of the time, your luck will even out, so in most realistic scenarios you’d probably have to do 900 or so comparisons, but definitely not thousands. At large scales, the quicksort is much quicker than the thousands of comparisons you would need to do to execute the bubble sort or insertion sort.
We still have to do N comparisons for each step of the quicksort — but this time, the number of steps is proportional to log N. We can say that the time complexity of the quicksort, at least most of the time when we don’t get really unlucky with choosing our pivots, is O(N * log N).
Merge Sort
The merge sort is a bottom-up sorting process. You start by breaking down the list into small chunks, and sort each chunk. Then, you combine the already-sorted chunks back together to give you a sorted list. Once again, our starting list:
Step 1: This time, let’s split the list into pairs from left to right, and make sure to swap each pair if needed to get it into the right order. As it turns out, we need to swap Rattata and Gyarados, and also Jigglypuff and Bellsprout. You can now think of each pair as a mini-list of two Pokemon that’s been sorted.
Step 2: Next, we take the first two chunks — the pairs 015/145 and 016/149 — and merge them into a sorted list of four Pokemon. It will take three comparisons to do this:
015 becomes before 016. 015 goes at the front of the list.
016 comes before 145. 016 goes next.
145 comes before 149. 145 goes next.
Leaving us with this (let’s call this sublist A):
We can do the same to merge the 019/130 and 039/069 pairs. Let’s call this sublist B.
And the same to merge the last two pairs, 025/142 and 006/143. Let’s call this sublist C.
Step 3: Now we have three sublists A, B, and C which are each sorted. All we have to do now is merge the lists. We start by merging A and B, by comparing the first element of each list, pushing it to our new, bigger list.
015 comes before 019, start the list with 015
016 comes before 019, move 016 next
019 comes before 145, move 019 next
039 comes before 145, move 039 next
069 comes before 145, move 069 next
130 comes before 145, move 130 next
Then just add 145 and 149 at the end. No comparison needed since they’re already sorted.
Step 4: Now we can combine this sorted list of 8 Pokemon with sublist C to get the final result.
With the merge sort, it took us only four steps to assemble a sorted list of these 12 Pokemon. The total number of comparisons we needed to make was:
The merge sort takes about as long as the quicksort to execute. But what if we scale up? Turns out, it behaves much like the quicksort does.
When you double the list, you’ll need to add one more merge. So you only need one more step.
Quadruple the list length? Two more steps.
Eight times the list length? Three more steps.
Now for Professor Cypress’s original challenge — to sort all 151 Pokemon:
This is slightly slower than the best-case scenario for the quicksort. However, the merge sort is a guarantee. You don’t have to cross your fingers and hope you picked the right pivots. The sort will always take 7 steps and at most 880 comparisons.
The merge sort, like the quicksort, has a time complexity of O(N * log N) — because the number of steps we have to do is proportional to log N, and the number of comparisons in each step will never be more than N.
“Thank you Ash, that was a very thorough answer,” Professor Cypress finally said, as Ash drank several mouthfuls of water. “But yesterday, another candidate — I assume he’s some kind of friend of yours called Gary — told me that he had a way of getting all the Pokemon sorted without doing any comparisons at all! Is there an even faster way than these merge and quicksorts you’re telling me about?”
“Well,” sighed Ash, “Yes and no. It’s a long story”
To be continued … in Part 2
I referred to these resources while writing this article:
- Victor Adamchik’s course notes from Carnegie Mellon University
- Douglas Harder’s course notes from the University of Waterloo
[1]: For the remaining insertions, you would have to do:
- 145: 1 comparison
- 016: 2 comparisons
- 149: 3 comparisons
- 130: 3 comparisons
- 019: 3 comparisons
- 069: 4 comparisons
- 039: 4 comparisons
- 025: 4 comparisons
- 142: 8 comparisons
- 006: 1 comparison
- 143: 9 comparisons
Verifying this is left as an exercise for the reader.
