Sorting Algorithms

In future blog posts, I’d like to go in more depth about when to use recursion versus when to use sorting, searching, etc.

Right now I want to talk about sorting, specifically sorting algorithms. There are tons of them. With quick sort, you want to use this when your average case performance matters more than your worst case performance. Because quick sort allows you to sort in O(nlog(n)), but in worst case in O(n²).

But merge sort is great because it’s always O(nlog(n)). Although the space complexity is a little higher than quick sort, it’s definitely a useful sort.

There’s also insertion sort, selection sort, and bubble sort. Those are fun when you’re doing something quick and dirty and you want to just experiment around with sorting. But in real life, it’s less likely you’ll be using them.

In real life, it’s more likely you’re gonna use the framework, or the libraries or the languages sorting algorithm. Their advantage, is they’re fairly easy to implement in code.

Although, a side comment here, insertion sort is great for small or nearly sorted inputs.

During an interview where they might ask you to implement a sorting algorithm, which might happen to be a rare case, you could say something like because we have a time constraint, I’d like to use something slow like bubble sort instead of implementing something like merge sort, because its something we could easily implement with a library or fairly easily with documentation. Or we could use merge sort to divide and conquer the code to make it more efficient.

It’s good to implement something like bubble sort, but also to implement merge sort to make it more efficient. Talking like this can be highly advantageous in showing an interviewer that you have a grasp of these concepts related to implementing sorting algorithms in the real world.

You can look at sorting algorithms, and consider what’s best based on their speed, stability, and the readability and whether the input is already sorted or nearly sorted. How large is the input? You can make the right decision on the best sorting algorithms taking all of this into consideration.

This is all I’m gonna touch on for now. Until next time.

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://brilliant.org/wiki/sorting-algorithms/