Interview prep? Study smart by learning to summarize sorting algorithms
Sorts in 60 Seconds: Speedy JavaScript Interview Answers on Sorting
Developer interviews often ask about sorting algorithms — here is how to explain 10 different sorting algorithms in just 60 seconds.
There is no one sort to rule them all
Sorting algorithms can be a confusing topic, but they are a popular interview subject in software engineering jobs at all levels.
That’s because sorts are a great way to demonstrate whether you understand the trade-offs in selecting an algorithm, including computation time (also called complexity) and the space used (often called overhead).
First, some definitions — then we’ll define each sorting algorithm based on these 5 properties:
“The ideal sorting algorithm would have the following properties:
[✅] Stable: Equal keys aren’t reordered.
[✅] Operates in place, requiring O(1) extra space.
[✅] Worst-case O(n·lg(n)) key comparisons.
[✅] Worst-case O(n) swaps.
[✅] Adaptive: Speeds up to O(n) when data is nearly sorted or when there are few unique keys.
There is no algorithm that has all of these properties, and so the choice of sorting algorithm depends on the application.” —Sorting Algorithms on TopTal
Now on to the sorting algorithms: Insertion Sort, Selection Sort, Bubble Sort, Shell Sort, Merge Sort, Heap Sort, Quick Sort, Quick3 Sort, and Tim Sort.
Insertion Sort
“PROPERTIES
[✅] Stable
[✅] O(1) extra space
[❌] O(n²) comparisons and [❌] swaps
[✅] Adaptive: O(n) time when nearly sorted
[✅] Very low overhead” —Insertion Sort on TopTal
Insertion Sort is best for small problem sizes or nearly-sorted data.
- Jim Rottinger implements Insertion Sort in JavaScript in DailyJS:
Selection Sort
“PROPERTIES
[❌] Not stable
[✅] O(1) extra space
[❌] Θ(n²) comparisons
[✅] Θ(n) swaps
[❌] Not adaptive” —Selection Sort on TopTal
Selection Sort is best when swapping items is very costly.
- Kyle Jensen implements Selection Sort in JavaScript Algorithms:
Bubble Sort
“PROPERTIES
[✅] Stable
[✅] O(1) extra space
[❌] O(n²) comparisons and [❌] swaps
[✅] Adaptive: O(n) when nearly sorted” —Bubble Sort on TopTal
Bubble Sort is similar to Insertion Sort with slightly more overhead.
- Kyle Jensen also implements Bubble Sort in JavaScript Algorithms:
Shell Sort
“PROPERTIES
[❌] Not stable
[✅] O(1) extra space
[❌] O(n³/²) time […]
[✅] Adaptive: O(n·lg(n)) time when nearly sorted” —Shell Sort on TopTal
Shell Sort has low overhead and may be good for small data sets.
- Shingo Konnai implements Shell Sort in JavaScript in his Medium blog:
Merge Sort
“PROPERTIES
[✅] Stable
[❌] O(n) extra space for arrays […]
[❌] O(lg(n)) extra space for linked lists
[✅] O(n·lg(n)) time
[❌] Not adaptive
[✅] Does not require random access to data” —Merge Sort on TopTal
Merge Sort can be excellent if using O(n) extra space is OK.
Merge Sort is one of the only sorting algorithms with O(n·lg(n)) time complexity that is stable (equal keys aren’t reordered), and it is simple.
- Tim Han implements Merge Sort in JavaScript in Plain English:
Heap Sort
“PROPERTIES
[❌] Not stable
[✅] O(1) extra space […]
[✅] O(n·lg(n)) time
[❌ ]Not really adaptive” — Heap Sort on Toptal
Heap Sort is simple, fast, and sorts in-place, but it is not stable.
- Vaidehi Joshi implements Heap Sort in JavaScript in basecs:
Quick Sort (2-way Partition)
“PROPERTIES
[❌] Not stable
[❌] O(lg(n)) extra space […]
[❌] O(n²) time [worst case], but typically [✅] O(n·lg(n)) time
[❌] Not adaptive” Quick Sort on Toptal
Quick Sort is a good general-purpose sort with low overhead.
Quick Sort is a popular algorithm and considered by some to be optimal:
“Quicksort is optimal [because] The average number of compares per element varies within a constant factor of the entropy H.” — Robert Sedgewick and Jon Bentley in their talk Quicksort is Optimal
Quick Sort’s worst case O(n²) time happens with data already sorted in ascending or descending order, but O(n·lg(n)) time is more typical.
- Charles Stover implements Quick Sort in JavaScript on his Medium blog:
- And RosettaCode.org has an ES6 implementation of 2-way Quick Sort:
Quick Sort (3-way Partition) aka Quick3
“PROPERTIES
[❌] Not stable
[✅] O(lg(n)) extra space
[❌] O(n2) time [worst case], but typically [✅] O(n·lg(n)) time
[✅] Adaptive: O(n) time when O(1) unique keys” — Quick Sort 3 Way on Toptal
Quick3 is the preferred version of Quick Sort because it is adaptive.
Quick Sort (3-Way Partition) has slightly higher overhead compared to the 2-way partition version. Both have the same time bounds, but Quick3 is highly adaptive in the common case of sorting with few unique keys.
- Atin implements 2-way & 3-way Quick Sort in his Stack Overflow answer:
Bonus: Dual-Pivot 3-Way Quick Sort
Want to show off in your interview? Or just want an even-better version of one of the best general-purpose sorting algorithms, Quick Sort?
“When stability is not required, quick sort is the general purpose sorting algorithm of choice. Recently, a novel dual-pivot variant of 3-way partitioning has been discovered that beats the single-pivot 3-way partitioning method both in theory and in practice.” — Quick Sort 3 Way on Toptal
Dual Pivot Quick Sort is a bit faster than the original Quick Sort.
- GeeksforGeeks explains dual-pivot Quicksort with a C implementation:
Dual Pivot Quick Sort implemented in JavaScript
I couldn’t resist including the instructions to assemble this adorable IKEA “KVICK SÖRT” — follow along as he sorts that data:
- That illustration 😂 comes from a JavaScript implementation of Dual Pivot Quick Sort by developer aureooms available on GitHub and npm:
Why is Quick Sort considered the best all-around sorting algorithm?
Quick Sort is fast, flexible, and optimizable, making it popular even though it is not a stable sorting algorithm:
“Quicksort it is probably the most used sorting algorithm because it’s easy to implement on average, gives high efficiency for large-data applications, it can be optimized for different needs and it’s relatively flexible on it’s input data.
Quicksort is a logarithmic-time algorithm, in other words, it has a Big O notation of O(log n)-(more about Big O Notation)- and depending on the way you implement it, it can be up to 2x or even 3x faster than Merge Sort or Heap Sort.
Do note that the O(log n) speed is a best-case/average time, in worst case scenarios it can be O(n2) depending on the implementation.” —César Antón Dorantes in Cesar’s Tech Insights
Why is Quick Sort so popular? It’s on average a very fast algorithm.
I will cover one sorting algorithm that’s even faster later in this article.
But really — which is best?
- Bubble Sort has the best name. Bubble. Sort.
- Merge Sort is the best if extra space doesn’t matter.
- Heap Sort is the best if stability doesn’t matter.
- Quick Sort (3-way) is best general-purpose choice.
- Dual-Pivot (3-way) Quick Sort is the bleeding edge.
- Chrome uses something called Tim Sort (I’ll explain later).
Which algorithm is Array.sort() in JavaScript?
This is a surprisingly complicated question to answer, but usually Array.sort() uses Quick Sort or Merge Sort:
“Depending on the type of array, different sort methods are used:
Numeric arrays (or arrays of primitive type) are sorted using the C++ standard library function std::qsort which implements some variation of quicksort (usually introsort).
Contiguous arrays of non-numeric type are stringified and sorted using mergesort, if available (to obtain a stable sorting) or qsort if no merge sort is available.
For other types (non-contiguous arrays and presumably for associative arrays) WebKit uses either selection sort (which they call “min” sort) or, in some cases, it sorts via an AVL tree.” —Konrad Rudolph in his Stack Overflow answer
But that is just for Mozilla, as Chrome’s V8 JavaScript interpreter has moved on to Tim Sort, which I explain in the next section:
“There is no draft requirement for JS to use a specific sorting algorthim. As many have mentioned here, Mozilla uses merge sort.However, In Chrome’s v8 source code, as of today, it uses QuickSort and InsertionSort, for smaller arrays. […]
Update As of 2018 V8 uses TimSort, thanks @celwell. Source” —Joe Thomas in his Stack Overflow answer
So should you just use Array.sort() in your JavaScript code? Yeah, probably. But that’s not the answer to the interview question! 😁
Wait, What The Hell is Tim Sort?
If you were as surprised to learn of Tim Sort as I was, here’s the low down on the sort used by Array.sort() in Chrome’s V8 engine:
“Data structure Array
[✅] Worst-case performance O ( n log n )
[✅] Best-case performance O ( n )
[✅] Average performance O ( n log n )
[❌] Worst-case space complexity O ( n )
[✅] [Stable]” — Wikipedia
Wow, if that seems like quite an impressive algorithm, it’s because it is:
“Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.” — Wikipedia
Let’s look at a chart comparing Tim Sort to Quick Sort and Merge Sort:
Tim Sort is a blazing-fast, space-efficient, stable sorting algorithm.
Tim Sort is the algorithm of choice if using O(n) extra space is OK. If memory space is limited, then Quick Sort or Heap Sort may be better choices, as they have O(lg(n)) and O(1) space requirements respectively.
Watch animated sorting at Toptal
The site Toptal has a superb animation comparing the 8 sorting algorithms explored here using 4 different types of data. Here’s a screenshot:
For me, it really reinforced the point that Quick3 is adaptive — standard Quick Sort takes forever on the few unique keys data in comparison to Quick3.
Watch animated sorting at SORTING.at
The site SORTING.at also has excellent animation comparing sorting algorithms. Their engine featuring the following sorting algorithms:
I found SORTING.at’s animation to be especially soothing, and it is a great way to compare individual sorting algorithms to each other.
Recap: Summarize 10 Sorts in 60 Seconds
We covered a total of 10 sorting algorithms in this article. Here is the take-home point for each one:
- Insertion Sort is best for small problem sizes or nearly-sorted data.
- Selection Sort is best when swapping items is very costly.
- Bubble Sort is similar to Insertion Sort with slightly more overhead.
- Shell Sort has low overhead and may be good for small data sets.
- Merge Sort can be excellent if using O(n) extra space is OK.
- Heap Sort is simple, fast, and sorts in-place, but it is not stable.
- Quick Sort is a good general-purpose sort with low overhead.
- Quick3 is the preferred version of Quick Sort because it is adaptive.
- Dual Pivot Quick Sort is a bit faster than the original Quick Sort.
- Why is Quick Sort so popular? It’s on average a very fast algorithm.
- Tim Sort is a blazing-fast, space-efficient, stable sorting algorithm.
Non-comparison sorting algorithms
As a final technical note, I should mention that I only examined comparison sorting algorithms.
There are also non-comparison sorting algorithms such as Bead Sort (or Gravity Sort), Bucket Sort (or Bin Sort), Counting Sort, and Radix Sort.
Non-comparison sorting algorithms can have a lower bound of O(n), compared to O(n·lg(n)) for comparison sorting algorithms, because non-comparison sorts make certain assumptions about the data.
Thus every non-comparison sort has certain requirements for its use.
Now get out there and Quick Sort, Tim Sort, or just sort how you want to!
Further Reading
- Want to see all these sorting algorithms in one place? JavaScript developer amhatami has Node.js implementations on GitHub and npm:
- Bonvic bundi explains Big-O notation in detail in Better Programming:
- GeeksforGeeks suggests some reasons why Quick Sort beats Merge Sort:
- GeeksforGeeks shows arrays and linked lists benefit from different sorts:
- Rohan Paul compares two JavaScript implementations of Quick Sort in JavaScript in Plain English:
- Brandon Skerritt discusses Timsort in-depth on Brandon’s Blog:
Dr. Derek Austin is the author of Career Programming: How You Can Become a Successful 6-Figure Programmer in 6 Months, now available on Amazon.