Sorting & Efficiency

I may be so bold as to say that everything we have done so far in this course has been about efficiency. The very nature of computing information is limited foremost by the resources you have to compute said information.

Hence, a computer which spends an hour doing something another computer can do in five minutes is going to be an inferior computer. However, a computer which can't run a code that another computer can run is perhaps not a question of better or worse computer, but of better or worse code.

And so we come to a question of efficiency, and one of the most important places for efficiency: sorting.

Once again I'm going to use a real-life analogy. If you have a bajillion eggs and you need one particular egg (probably because you're a crazy person), it would be horrible to look through each individual egg. However, if the eggs were, say, organized by colour or mass, then already you can discard any egg that isn't the colour or mass of the one you're looking for.

Heck, there are robots that do this for Lego bricks. But what of code, then?
Well,  code is wonderful for coming up with ways to sort things because there are a lot of different ways you can create a code to sort things.
Nonetheless, if we are indeed searching through our eggs, what is the best way to organize a hodge-podge batch, barring Rube Goldberg-esque machinery antics (as seen above)?
Well let's say for convenience all the eggs are lined up. We can compare each egg and place smaller ones to the right of larger ones (bubblesort), but there's no way you would be willing to just swap two eggs every time until you cover all the eggs - that would take forever with a bajillion eggs!
On the other end of the spectrum, you could divide up the eggs around the most average egg (quicksort), and then find the most average egg in each division and sort out which eggs are larger and which eggs are smaller. That goes much faster since you are working with smaller and smaller values-- wait, something smells like recursion!

Yes, that beautiful aroma of recursion is back. While something like grabbing two eggs and swapping them is all fine and well, it requires many attempts, usually as many as there are eggs - hence eggs squared to get through the entire thing. Yuck.
Rather, with quicksort or mergesort, we can look at smaller and smaller sets of eggs. When we work backwards, we can compare the sets and quickly organize them again, thereby finishing with a big sorted line of eggs after much less time since we are dividing the eggs into smaller sets (logarithmically smaller sets!).

Thus, efficiency is perhaps the most crucial part of sorting giant amounts of information (smaller sets can, of course, use more performance if the information needs to be found more quickly). With well-crafted code, and often recursion, it is possible to vastly reduce the amount of work we need to do when sorting or looking at other problems which require high efficiency. And so we can sort our eggs so much faster than before.