Merge Sort
How it works
- Divide the unsorted list into n sublists,
- Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining
Source: wikipedia
Performance
- Best case performance: Time complexity O(n log n),
- Average case performance: Time complexity O(n log n),
- Worst case performance: Time complexity O(n log n),
Let’s implement the mergesort in the javascript
const merge = (leftArray, rightArray) => {
var sortedArray = [];
while (leftArray.length && rightArray.length) {
if (leftArray[0] <= rightArray[0]) {
sortedArray.push(leftArray[0]);
leftArray = leftArray.slice(1)
} else {
sortedArray.push(rightArray[0]);
rightArray = rightArray.slice(1)
}
}
while (leftArray.length)
sortedArray.push(leftArray.shift());
while (rightArray.length)
sortedArray.push(rightArray.shift());
return sortedArray;
}
const mergeSort = (arr) => {
if (arr.length < 2) {
return arr;
}
let midpoint = parseInt(arr.length / 2);
let leftArray = arr.slice(0, midpoint);
let rightArray = arr.slice(midpoint, arr.length);
return merge(mergeSort(leftArray), mergeSort(rightArray));
}
var unSortedArray = [3, 6, 3, 4, 2, 7, 3, 1, 2, 3, 8];
let sortedArray = mergeSort(unSortedArray);
console.log(sortedArray);
// output
// [1, 2, 2, 3, 3, 3, 3, 4, 6, 7, 8]