Merge sort
Description
The merge sort algorith uses a Devide and Conquer approach to sort elements. The basic idea is that an array of 1 element is sorted. So, if we have an array with more than 1 element we just need to devide that element in half, until we get multiple 1 element arrays. Once we have all the 1 element arrays, we need to merge them back again but in order. We'll repeat this for the array and all the sub arrays.
1. Verbose implmentation
0
1
1. Minimal implmentation
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/*
While there are elements on the left and righ arrays,
push the smallest one into the merged array until both
left and right are empty.
*/
const mMerge = (left: number[], right: number[]): number[] => {
const merged: number[] = [];
while(left.length && right.length) {
merged.push( left[0] <= right[0] ? left.shift()! : right.shift()!);
}
return merged;
};
/*
Calculate the middle index of the array. Use that index
to divide the array into left and right. Use the Merge
function with the left being MergeSort(left) and right
being MergeSort(right);
*/
const mMergeSort = (array: number[]): number[] => {
if(array.length < 2) return array;
const mid = Math.floor(array.length/2);
const left = array.slice(0, mid);
const right = array.slice(mid);
return mMerge(mMergeSort(left), mMergeSort(right));
};