Course launching November 17, 2020
Follow me on YouTube for free coding interview videos.
Users who sign up for the email list will receive an exclusive 75% discount at launch.
Sorting is an incredibly important topic in computer science, and many academics devote their career to the topic. In interviews, it's often a key piece of information in a problem. It's not common to need to implement sorting from scratch in an interview, but it is helpful to understand some of the more popular options at a high level. The three important points to know:
- Sorting is assumed O(n log n)
- Know how to use the native sorting functionality in your language of choice
- Understand the Implications of Sorted vs. Unsorted Data
- Special case of O(n) for bucket sort
We'll cover these points more in-depth below.
Sorting in Interviews
1. Sorting is Assumed O(n log n)
It's up to your language or even the implementation of the language to decide which version sort algorithm to use. However, you can assume they'll use a O(n log n) version like merge sort.
For your interviews, it's unlikely that you will need to know how to write a sorting algorithm from scratch. If you use a built-in sort function, you'll just need to acknowledge that your sorting will add O(n log n) time complexity.
2. Sort in Your Chosen Language
You need to be able to sort for any data type in your language. This could be arrays numbers, strings, or even objects.
3. Understand the Implications of Sorted vs. Unsorted Data
If you are told the data is already sorted, then this is often an indication you can use the information to improve on your time complexity, with a very common way being binary search.
If the data is unsorted, then applying a sort to it can improve on a O(n2) or worse solution. Sorting the data can also make it more logical and easier to work with.
4. Bucket Sorting
Your data can be divided into pre-defined buckets, and in this case you can actually sort in O(n) time. You perform one pass over the data to fill your buckets, and then one pass over the buckets to form your output.
This is similar to radix sort, but bucket sort is a little more simple to conceptualize and implement. Creating simple buckets is likely all you will need in an interview.
Popular Sorting Algorithms
It's unlikely you'll need to implement one of these from scratch, but it's helpful to understand which have the best runtimes and how they work. Below are some of the most popular sorting algorithms. We mention the average and worst case because the arrangment of the items in the array can severely impact the runtime, but you are still safe to assume it's O(n log n) for your native sort implementation.
Avg & Worst Time: O(n2) | Space: O(1)
Selection sort is very inefficient but the easiest to understand. In nested loops, you find the smallest element and move it to the front. Then you find the second smallest and move it to the second spot. You repeat this until all the items are sorted.
Avg & Worst Time: O(n2) | Space: O(1)
Bubble sort is also very simple. It iterates through the array and checks each element with the one after it and swaps them accordingly. It will take O(n2) passes over the input data structure to get it entirely sorted.
Avg Time: O(n log n), Worst Time: O(n2) | Space: O(n log n)
Quick sort is also a "good" sorting algorithm at O(n log n). However, at worst case it can be O(n2) when the partition element is not near the median.
Quick sort works picking a random element and items are swapped based on whether they are larger or smaller than the partition element.
Avg & Worst Time: O(n log n) | Space: O(n log n)
Since merge sort is O(n log n), it is viewed as one of the "good" sorting algorithms. Merge sort repeatedly divides the arrays in half until you reach just two elements. It then sorts these elements and begins merging the arrays back together and sorts them at each merge.
Table of Contents