If Sorting Algorithms Were Pokemon
Gotta sort ’em all.
Sorting a list is a common introductory problem when studying algorithms. You can sort lists of numbers, letters or even words, but let’s consider the simple problem of sorting a list of integers: myList = [55, 29, 98, 61, 7, 31, 20, 68, 93, 10] .
It seems like a trivial task, but there are numerous methods to sort this list — and our choice of sorting algorithm starts to matter when the list gets longer, we have limited available memory, and we don’t want to spend an entire day stirring Poffins while we wait for the list to be sorted. ⏳
So, before you get all excited and exclaim “Selection Sort, I choose you!” on a list of 10 million integers, let’s take a look at your options and examine some of the most popular sorting algorithms out there today!
Insertion Sort = Squirtle
Insertion sort is efficient when sorting small lists; it makes a good starter algorithm, just like Squirtle, who science has shown is your best choice for a starter Pokemon. But with longer lists, insertion sort can get slow really fast; you better evolve before you hit the Elite Four.
How it works: A marker moves along the list, with elements already sorted to the left of the marker, and unsorted elements to the right. As a new element is reached, it is inserted back into the sorted portion of the list in the correct place, until all elements are sorted.
Selection Sort = Bulbasaur
The effectiveness of grass types against the first two gym leaders means that Bulbasaur is a natural choice if you want to start off easily. Selection sort is certainly easy to implement, and it’s how most people would intuitively sort a deck of cards. This algorithm searches for progressively larger numbers, in time with Bulbasaur’s bulb growing as it absorbs sunlight. But honestly, this algorithm is too slow for any practical application. Keep it in your PC at the nearest Pokemon Centre, it may come in handy in the future…
How it works: Selection sort makes a pass through the list, finds the smallest element, and places it in its correct spot, at the beginning of the list. It repeats this, swapping the next smallest element into position in the sorted list, continuing until all elements are sorted.
Bubble Sort = Magikarp
It might be a good way to demonstrate a sorting algorithm, but bubble sort has become a bit of a joke. It’s been described as an insult, too slow for any practical use, and a pathetic excuse for a Pokemon. Oh wait, was I talking about bubble sort or Magikarp?
How it works: Bubble sort steps through the list, comparing each pair of adjacent elements, and swaps them if they are in the incorrect order. It continues swapping until the list is sorted.
Merge Sort = Mewtwo
Finally, an algorithm powerful enough to be suitable for a legendary Pokemon. Mewtwo was bred especially for battle after years of gene splicing and DNA engineering. Which is basically just cutting DNA into smaller pieces and merging them back together in the order you want… right? But beware, you’ll need a master ball to store this one — an unoptimized merge sort requires memory to store both the input and output arrays.
How it works: Merge sort is known as a divide and conquer strategy. The algorithm splits a list in half, and recursively calls merge sort on both halves (splitting it again). By definition, a list of 0 or 1 elements is sorted, forming the base case. Once both halves of a list are sorted through recursive calls to merge sort, the two halves are merged in order. Merging continues until the sorted list is completed.
Quicksort = Eevee
Quicksort is probably one of the most popular sorting algorithms in place today. Eevee’s cuteness makes it one of the most well-known Pokemon, aside from Pikachu, for trainers and non-trainers alike. But there’s something you need to watch out for; Eevee has an unstable genetic makeup, which is what leads to its many possible evolutions. Also, keep your Eevee out of sight of fighting type Pokemon; if you’re not careful, its worst-case performance can be risky.
How it works: Quicksort is another divide-and-conquer algorithm. It picks an element to use as a pivot, and then partitions the list by swapping elements to the appropriate side of the pivot. Subsequent pivots are chosen, and the list is partitioned, until the list is sorted.
Heapsort = Venusaur
I told you that Bulbasaur would come in handy! Heapsort is an improved version of selection sort, that makes use of a heap (a type of binary tree) to sort the list. And when you need to switch the max value root to a leaf and cut it off for your sorted list, Venusaur’s Razor Leaf has got your back.
How it works: Heapsort first creates a heap of the unsorted list. A heap is a binary tree data structure where:
- Each node is greater than each of its children
- The tree is perfectly balanced
- All leaves are in the leftmost position available
The algorithm then creates a sorted array by repeatedly removing the largest element from the heap, inserting it into the array, and fixing the heap.
Counting Sort = Zubat
I don’t know why Zubats are everywhere. But their tendency to travel in groups works well for a counting sort, which is most effective when you have a relatively small set of keys with multiple values of each.
How it works: Counting sort works by counting the number of objects that have distinct key values (kind of hashing). It then uses the count of the number of that object to determine its place in the sequence. To simplify this, if your list was 1, 3, 1, 2, 3, 1, you would know that, because you have three 1’s, the next key (2) would be placed into the list at 3 + 1 (4).
Radix Sort = Caterpie
Caterpie is another Pokemon that you just can’t help running into in large quantities. This bug Pokemon is #10 in your Pokedex… a great number to use as a base for your radix sort! It’s segmented body can help you as you’re counting integers to sort your list.
How it works: Radix sort sorts the list digit by digit, starting from the least significant digit to the most significant digit. It makes use of the counting sort algorithm by creating buckets for individual digits. For example, 23, 12, 21, 14 would be sorted by the 1s digit first [21, 12, 23, 14], followed by the 10s digit [12, 14, 21, 23].
Sleep Sort = Snorlax
Zzzzzzzzzzz. This is probably not how you should sort a list. Try this on an exam or at an interview, and a wild Snorlax will block your path (to any chance of success).
How it works: Sleep sort creates a different thread for each element in the list, and then sleeps each thread for a length of time proportional to the element. The thread with the least amount of sleeping time (i.e. the smallest element) wakes up first, and is printed first. Elements “wake up” in order!
I’m going to let Alakazam figure out the code for this one.
Twitter Sort = Chatot
This Pokemon speaks for itself. Literally. When in doubt, ask humans.
How it works: Someone wrote an algorithm that uses the Twitter API to tweet a request with your list of numbers, asking for someone to sort them. When someone replies with a sorted list of the numbers, the result is returned.
You can find the implementation of the algorithm here.
Bogosort = Togepi
Don’t try this at home. Bogosort randomly shuffles a list, and then checks if it is sorted. Much like Togepi’s Metronome move, maybe you get something good… maybe you get something terrible. It’s a good thing Togepi is known to bring good luck — you’ll need it.
There’s really no point in writing this. Please never use this. If you really must know, the algorithm looks something like this:
These are some of the most common (plus a few absurd) algorithms you could use to sort a list. Oh, but we never actually checked what happened! Any of these algorithms will return our sorted list… myList = [7, 10, 20, 29, 31, 55, 61, 68, 93, 98] . Professor Oak would be proud!
When you are choosing which sorting algorithm to use in practice, you need to consider features such as stability, time complexity and space complexity, and how these change with the length of the list n. Whether a list begins almost mostly sorted, sorted in reverse, or entirely out of order can effect whether the algorithm performs at its best case or worst case.
Having a great understanding of all these different sorting algorithms can come in handy — you never know when you’ll be walking through tall grass and a wild unsorted list may appear! Best to be prepared 😉.
Last week at The Recurse Centre, I spent some time learning about data structures and algorithms. If you’re interested in learning more, UC Berkeley’s CS61BL class and Problem Solving with Algorithms and Data Structures in Python were great resources. That’s Part Two! ✅👩🏼💻
