MergeSort

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

    // Split the array into two halves
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));

    // Merge the sorted halves
    return merge(left, right);
}

function merge(left, right) {
    let sortedArray = [];
    let i = 0, j = 0;

    // Merge the two sorted arrays
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            sortedArray.push(left[i]);
            i++;
        } else {
            sortedArray.push(right[j]);
            j++;
        }
    }

    // Copy remaining elements from left (if any)
    while (i < left.length) {
        sortedArray.push(left[i]);
        i++;
    }

    // Copy remaining elements from right (if any)
    while (j < right.length) {
        sortedArray.push(right[j]);
        j++;
    }

    return sortedArray;
}

// Example usage
const array = [1, 7, 2, 8, 3, 5, 6];
const sortedArray = mergeSort(array);

console.log(sortedArray); // Output: [1, 2, 3, 5, 6, 7, 8]