Sorting is one of the most common solutions when we want to extract some insights about a collection of data. We can sort to get the maximum or minimum value and many algorithmic problems involves sorting data first.
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 so we can be aware of the side-effects it will have 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 especially 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 other auxiliary memory because it moves the items in the collection itself. No requiring extra memory for sorting is especially useful for 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 many algorithms some of them simple and other 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(n2) |
O(n log n) |
O(log n) |
Yes |
Yes |
No |
No |