There are tons of sorting algorithms. Which one is best? When should you use a particular sorting algorithm?
What if you were asked in an interview what sorting algorithm would be best if you had the user data for 20 million names that need to be sorted.
Let’s go over some rules… Such as when to use insertion sort.
Insertion sort should only be used with a few items. If your input is small or items are mostly sorted, it’s really fast. It uses very little space and most importantly, it’s really easy to implement in code. So remember this, only a few items and mostly sorted data… you should use insertion sort.
What about bubble sort? To be honest, you’re really never going to use bubble sort. It’s really only used for educational purposes as a way to teach sorting. But it’s very rare you’ll find this in real life because it’s not very efficient.
What about selection sort? Same thing with selection sort, it’s numbers / efficiency isn’t very good so you’re not gonna use it much. Mainly it’s being used as a teaching mechanism. It is important to build a foundation though, so it’s good to know it.
Talking about merge sort, it’s really good because of divide and conquer. We have O(n log(n)). It’s really fast and it’s worst case, average case, and best case are the same. We can always divide up a list evenly. This is not the case for most algorithms. If you’re worried about worse case scenarios, then merge sort is the way to go.
However, if you want to sort in memory on your machine and you’re worried about space complexity, merge sort is going to be really expensive. It uses space complexity of O(n). However if you had huge files that can be sorted in memory so you have external sorting that you need, maybe like a process outside of memory, it’s suitable for external sorting. Then merge sort is good because we won’t care so much about space complexity.
What about quick sort? Quick sort is actually better than merge sort, right? It actually has less space complexity than merge sort and its average and best case are equivalent to merge sorts time complexity. It’s probably one of the most popular sorting algorithms. But the one downside is the worst case. If you don’t pick the pivot properly, you can have some really slow sorting. So you have to be careful and if you’re really worried about worst case, then you’d rather pick something else.
How about heap sort? It’s very similar to quick sort and merge sort but it has a space complexity of O(1). Isn’t this better then all of the above? Well, it can sort in place and doesn’t have the worst case quadratic behavior that quick sort has or the memory usage that merge sort has. But on average, it’s actually slower then quick sort in most cases. It’s one of those things where with heap sort, unless you’re really really worried about worst case and memory, then you might use it, but in most cases you are gonna use just quick or merge sort.
What about bucket sort, radix sort, counting sort? Why don’t we talk about these since they look really good in terms of time complexity compared to what we’ve already talked about? I will discuss more in future blog posts about this.
And as always, I highly recommend the Zero to Mastery Academy to improve your own personal skills as a programmer as this is where all this information was drawn from and Andrei Neagoie, the founder and lead instructor, has been a true mentor to me.
Photo credit: https://medium.com/@george.seif94/a-tour-of-the-top-5-sorting-algorithms-with-python-code-43ea9aa02889
