Sorting is one of the most common solutions when we want to extract some insights about data. We can sort to get the maximum or minimum value, and many algorithmic problems can benefit from sorting.
Before we dive into the most well-known sorting algorithms, let’s discuss the sorting properties.
Sorting implementations with the same time complexity might manipulate the data differently. We want to understand these differences to be aware of the side effects on data or extra resources they will require. For instance, some solutions will need auxiliary memory to store temporary data while sorting, while others can do it in place.
Sorting properties are stable, adaptive, online, and in-place. Let’s go one by one.
An stable sorting algorithms keep the relative order of items with the same comparison criteria.
This incredibly useful when you want to sort on multiple phases.
const users = [
{ name: 'Bob', age: 32 },
{ name: 'Alice', age: 30 },
{ name: 'Don', age: 30 },
{ name: 'Charly', age: 32 },
];name, you would have:[
{ name: 'Alice', age: 30 },
{ name: 'Bob', age: 32 },
{ name: 'Charly', age: 32 },
{ name: 'Don', age: 30 },
];Then, here comes the critical part; if you sort by age, you might get (at least two) different results.
name:[
{ name: 'Alice', age: 30 },
{ name: 'Don', age: 30 },
{ name: 'Bob', age: 32 },
{ name: 'Charly', age: 32 },
];[
{ name: 'Don', age: 30 },
{ name: 'Alice', age: 30 },
{ name: 'Charly', age: 32 },
{ name: 'Bob', age: 32 },
];Both results are sorted by age; however, having a stable sorting is better if you want to keep the relative position of data with the same value.
An in-place sorting algorithm would have a space complexity of O(1). In other words, it does not use any additional memory because it moves the items in-place. No extra memory for sorting is especially useful for large amounts of data or in memory constraint environments like robotics, smart devices, or embedded systems in appliances.
It can sort a list as it receives it. Online sorting algorithms don’t have to re-sort the whole collection for every new item added.
Algorithms with adaptive sorting run faster, close to O(n), on an already sorted (or partially sorted) collection.
We explored the most common sorting algorithms, some of which are simple and others more performant. Also, we cover the properties of sorting algorithms such as stable, in-place, online, and adaptive.
Algorithms |
Comments |
Swap pairs bubbling up largest numbers to the right |
|
Look for biggest number to the left and swap it with current |
|
Iterate array looking for smallest value to the right |
|
Split numbers in pairs, sort pairs and join them in ascending order |
|
Choose a pivot, set smaller values to the left and bigger to the right. |
Algorithms |
Avg |
Best |
Worst |
Space |
Stable |
In-place |
Online |
Adaptive |
O(n2) |
O(n) |
O(n2) |
O(1) |
Yes |
Yes |
Yes |
Yes |
|
O(n2) |
O(n) |
O(n2) |
O(1) |
Yes |
Yes |
Yes |
Yes |
|
O(n2) |
O(n2) |
O(n2) |
O(1) |
No |
Yes |
No |
No |
|
O(n log n) |
O(n log n) |
O(n log n) |
O(n) |
Yes |
No |
No |
No |
|
O(n log n) |
O(n log n) |
O(n2) |
O(log n) |
No |
Yes |
No |
No |
so-1) Given an array of intervals [start, end], merge all overlapping intervals.
Common in interviews at: Facebook, Amazon, Bloomberg.
Starter code:
link:../../interview-questions/merge-intervals.js[role=include]Examples:
merge([[0, 2], [2, 4]]); // [[0, 4]] (0-2 overlaps with 2-4)
merge([[2, 2], [3, 4]]); // [[2, 2], [3, 4]] (no overlap)
merge([[1, 10], [3, 4]]); // [[1, 10]] (1-10 covers the other)Solution: [sorting-q-merge-intervals]
so-2) Given an array with three possible values (0, 1, 2), sort them in linear time, and in-place. Hint: similar to quicksort, where the pivot is 1.
Common in interviews at: Amazon, Microsoft, Facebook.
Starter code:
link:../../interview-questions/sort-colors.js[role=include]Examples:
sortColors([0, 2, 1]); // [0, 1, 2]
sortColors([2, 0, 2, 1, 0, 1, 0]); // [0, 0, 0, 1, 1, 2, 2]
sortColors([1, 1, 1]); // [1, 1, 1]Solution: [sorting-q-sort-colors]