The third chapter of Algorithms to Live By is about sorting. Some examples of sorting you might encounter:
- Ordering books on a shelf (if you still have physical ones)
- Participating in a tournament orders individuals/teams by skill (with varying degrees of reliability)
- Sorting food in your fridge so you know where to look for things
With more digitization these days, computers will handle most of the mundane sorting like ordering documents, but it’s interesting to realize how we naturally follow some of these algorithms. Let’s take an example of ordering your todo list by priority:
- Bubble sort - Look at two items on your todo list at a time, figure out if one is more important and swap them if needed. Keep going through the list (possibly multiple times) until everything looks in order. This is pretty inefficient, the time it takes will increase exponentially when you have more items in the list.
- Insertion sort - Order items as you look through. For each item, look back at what you’ve already sorted and place it between items of lower and higher priority. Unfortunately, even if it sounds smarter, it is also exponential.
- Merge sort - Divide the list into even groups, order each group. Build larger ordered groups by combining the smaller ones, until the whole list is sorted. This is slightly better, it is O(NLogN) time complexity in Big O. In other words, for each item in the list, you’ll probably have to compare/swap it more than once, but not with every item in the list.
- Bucket sort - Decide on groups of items as fine-grained as you can, like your todo list for today, tomorrow, this week, etc. making sure the buckets don’t overlap and that the buckets themselves have a natural order. In the ideal case where you have one bucket for each item, then you will only have to go through the list once.
As you can see, there’s many ways to accomplish sorting a todo list that you probably already have done in some form. One thing missing from this calculation, though, is how do you actually compare item priority? With books it’s easy to just alphabetically sort, but what about comparing “buying groceries” vs “doing your taxes”? If you’re completely out of food, then groceries will be a high priority, but if it’s the last day to file taxes, then maybe you should do that first to avoid a hefty penalty.
Sorting in real life situations is very personal, and prone to errors, so efficiency might not be the real issue. Maybe you like to put eggs on the top shelf of the fridge, and your significant other likes to put them on the bottom self, as long you pick one way to do it then it doesn’t matter where it goes. Deciding what todo list item is more important can be subjective, but if you just do one of them, then you don’t have to decide for that one at all. Maybe the best way to improve your sorting speed is by having less to sort, or not doing it at all.