Sorting | Skilled.dev
Learn

Sorting

Course launching August 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.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

Implementing a sort from scratch is not very common in interviews. The three important points to know:

  1. Sorting is assumed O(n log n)
  2. Know how to use the native sorting functionality in your language of choice
  3. Special case of O(n) for bucket sort

We'll cover these points more in-depth below.

Do I need a cheat sheet?

Sorting in Interviews

ARE THESE GIFS BETTER? https://visualgo.net/en/sorting

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 interview, it's very unlikely that you would need to know how to do write any sort from scratch. You 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.

In JavaScript, the sort can be deceiving, so it's essential to use the callback function. It converts all elements to strings and comparies their sequence of UTF-ecoded characters.

// Possibly unintuitive
[1, 50, 10000, 510, 5050, 60].sort() // [1, 10000, 50, 5050, 510, 60]

// Use the callback function which you can return numbers or booleans from
[1, 50, 10000, 510, 5050, 60].sort((a, b) => a - b) // [1, 50, 60, 510, 5050, 10000]

// Strings sort as expected
['March', 'Jan', 'Feb', 'Dec'].sort() // ["Dec", "Feb", "Jan", "March"]

// Use the callback function to handle objects
[{ score: 20 }, { score: 100 }, { score: 5 }].sort((a, b) => a.score - b.score)
// => [{ score: 5 }, { score: 20 }, { score: 100 }]

3. Bucket Sorting

Your data can be divided into pre-defined buckets, and in this case you can actually sort in O(kn) time. Here, n is the number of elements and k is the number of passes.

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.

Selection Sort

Avg & Worst Time: O(n2) | Space: O(1)

Selection sort is very inneficient 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.

Bubble Sort

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.

Quick Sort

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.

Merge Sort

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.

Prev
Searching and Binary Search
Next
Shifted Search

Table of Contents