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

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]