Merge Sort

• Merge Sort is another efficient divide-and-conquer sorting algorithm.It divides the array into two halves, sorts them, and then merges them back together.
• Merge Sort also has an average time complexity of O(nlog n) and is stable, making it suitable for various scenarios.

  
    function mergeSort(arr) {
       if (arr.length <= 1) return arr;

        const middle = Math.floor(arr.length / 2);
        const left = arr.slice(0, middle);
        const right = arr.slice(middle);

        const merge = (left, right) => {
            let result = [];
            let leftIndex = 0;
            let rightIndex = 0;

            while (leftIndex < left.length && rightIndex < right.length) {
                if (left[leftIndex] < right[rightIndex]) {
                    result.push(left[leftIndex]);
                    leftIndex++;
                } else {
                    result.push(right[rightIndex]);
                    rightIndex++;
               }
            }

            return result.concat(left.slice(leftIndex), right.slice(rightIndex));
        };
        return merge(mergeSort(left), mergeSort(right));

    }

    const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
    const sortedArray = mergeSort(unsortedArray);