Why yes, I am going to keep mining that article about stuff you should know for programming interviews for blog post ideas :) While I don’t think that a lot of the common interview concepts from that article are actually worthwhile to ask about in an interview, I do think they’re interesting bits of nerd trivia and going in depth into how stuff works shows that nothing the computer does is magic.
Sort algorithms in particular are a weird interview question because you should basically never implement one at work. There are always edge cases, but in general if you actually write a sort function you have done something bad and you should feel bad. The correct way to implement a sort function is to import a library and go on with your day.
That said, sort algorithms are interesting in their own right. They’re one of those things that seem incredibly simple and boring until you start thinking about how you would tell a computer how to sort things. There are also way more sort algorithms than you might think, all with their own pros and cons.
Quick sort uses a divide and conquer strategy – instead of sorting the entire array you give it, it picks a pivot point (different implementations do this in different ways, one of the simplest methods is just to take the middle element of your array), rearrange the elements of your array so that everything less than the pivot is on the left and everything greater is on the right. Then you break the array into halves and recursively search each one until everything in the array is in order. There’s a really helpful gif at the top of the wikipedia article about quicksort that explains it better.
Because quick sort rearranges the array elements by swapping them, it requires very little memory, which was a big deal when it was invented by Tony Hoare in 1959. To this day it’s one of the fastest sorting algorithms, provided you do a good job of picking your pivot point. If you do a bad job of that things go off the rails, particularly if your array is mostly sorted already. In that case quick sort can (if you don’t check for a sorted or mostly sorted array) effectively unsort and resort your array which is pretty slow, surprisingly enough.
Another efficient (in this case it’s a technical term for sort algorithms that are efficient enough to actually use) sort algorithm is merge sort. Merge sort is even older than quick sort, it was invented in 1945 by John von Neumann. Like quick sort, it uses a divide and conquer strategy, the difference is that merge sort divides the array into the smallest pieces it can, then merges those pieces into two element arrays, then merges those into four element arrays and so on until it produces a completely sorted array. As usual, wikipedia has a gif that explains it visually.
Merge sort requires much more memory than quick sort does because of the way it creates new arrays while it’s sorting. This can be an issue if you’re sorting especially large arrays, although I’m sure more advanced algorithms based on merge sort can do some sort of trickery to mitigate that :) On the upside, it’s a stable sort – if you have two objects in the array with the same sort order, they’ll stay in that order – unlike quick sort. It’s also good at handling slow sequential media like tape drives and handling linked lists, which quick sort is slow at and heap sort can’t handle at all.
Heap sort, the last sort algorithm I want to talk about today, is an interesting one. Unlike quick sort and merge sort, heap sort puts all the elements of the array into a heap first, then uses that to sort the array.
Quick digression from sorting: a heap is a partially ordered tree structure. In a heap, the child nodes are always less than (in a min heap, or always larger in a max heap) the parent node, but siblings aren’t in any particular order relative to each other. The root node is always the largest or smallest element in the heap, and if you remove it the heap rebalances itself so the next largest or smallest element becomes the new root.
Back to heap sort: once you have a heap it’s very simple, you just take the root, add it to your array, let the heap rebalance itself, take the new root, and so on until your heap is empty.
In comparison with other sorts, heap sort is a little slower than quick sort on average but has better worst case performance. Merge sort has similar time bounds (average, best case, and worst case time it takes to sort an array), but takes up more memory because a heap sort can be done in place. On the other hand, merge sort is stabl, parallelizes well, and works on datasets too large to fit into memory at once, which neither quick sort not heap sort can do.
One last piece of trivia: the Timsort algorithm, implemented in 2002 by Tim Peters, is based on merge sort and insertion sort (a very simple sort algorithm) and is the standard sort function in Python and Java.
There’s a huge amount of detail I skipped over, I recommend poking around wikipedia if you’re interested in more detail about the many, many, many ways you can sort a list. Just don’t ask about them in interviews, because all you’ll learn by doing that is whether your interviewee looked them up beforehand :)