Merge sort is a sorting algorithm that uses a divide-and-conquer technique to sort a given list, which means it breaks down a problem into smaller parts in order to be simpler to solve.
Merge Sort starts by splitting the list into halves, and continues to split those sublists until only sublists with a single element are left. Then merge those sublists into sorted sublists, and continue doing so until end up with a single sorted list.
[4, 3, 2, 1];
| |
| |
Divide [4,3] [2,1]
| | | |
| | | |
[4] [2] [2] [1]
| | | |
| | | |
Conquer [2,4] [1,2]
| |
| |
[1, 2, 3, 4]
Implementation
This algorithm can be implemented with two functions, one to divide and another to merge :
1/**
2 * Function to merge
3 **/
4function merge(left: number[], right: number[]): number[] {
5 const sorted = [];
6
7 // until one of the sublists has a element, insert them into the sorted list
8 while (left.length && right.length) {
9 if (left[0] < right[0]) {
10 sorted.push(left.shift());
11 } else {
12 sorted.push(right.shift());
13 }
14 }
15
16 // one of the sublists can still have leftover elements, so we need to merge them
17 return [...sorted, ...left, ...right];
18}
19
20/**
21 * Function to divide
22 **/
23function mergeSort(list: number[]): number[] {
24 // base case
25 if (list.length <= 1) return list;
26
27 // split the list into two halves
28 let left = list.slice(0, list.length / 2);
29 let right = list.slice(list.length / 2, list.length);
30
31 left = mergeSort(left);
32 right = mergeSort(right);
33
34 // merge the sublists
35 return merge(left, right);
36}
37
38const unsorted = [5, 4, 3, 2, 1];
39const sorted = mergeSort(unsorted);
40console.log(sorted); // [1, 2, 3, 4, 5]
Merge Sort performs in O(n log n) in terms of time complexity, its space complexity is O(n) since it uses auxiliary arrays to store the sublists. Also, we can leverage multi-threading to implement Merge Sort, sorting each half in separated threads, for example. Moreover, we can combine Merge Sort with other sorting algorithms, for example, instead of splitting the list into single element sublists, we could split into small sublists with a few elements, and apply Insertion Sort to sort them.
