归并排序

归并排序通过以下步骤实现：

1. **分割**：将序列递归地分成两半，直到每个子序列只包含一个元素。
1. **合并**：将两个有序子序列合并为一个有序序列。

/**
 * 合并
 * @param {排序的数组} arr 
 * @param {最左边的下标} left 
 * @param {中间位置的下标} mid 
 * @param {最右边的下标} right 
 */
function merge(arr, left, mid, right) {
    // 获取左边数组和右边数组得容量
    let n1 = mid - left + 1;
    let n2 = right - mid;


    // 按照mid 把数组分割到两个数组当中
    let leftArr = [];
    let rightArr = [];

    for (let i = 0; i < n1; i++) {
        const element = arr[i + left];
        leftArr.push(element)
    }
    for (let i = 0; i < n2; i++) {
        const element = arr[i + mid + 1];
        rightArr.push(element)
    }


    // 按照从小到大挑出来
    // i 是左边的数组读取的位置
    // j 是右边的数组读取的位置
    // k 是arr数组的位置
    let i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] < rightArr[j]) {
            arr[k] = leftArr[i];
            i++
        }
        else {
            arr[k] = rightArr[j];
            j++
        }

        k++;
    }

    // 看左边右边的有没有排完
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

/**
 * 排序
 * @param {排序的数组} arr 
 * @param {最左边的下标} left 
 * @param {最右边的下标} right 
 */
function mergeSort(arr, left, right) {
    if (left < right) {
        let mid = parseInt((right + left) / 2)
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right);
        console.log("left: " + left + " mid: " + mid + " right: " + right)
    }
}


let arr = [12, 6, 13, 5, 14, 7];
mergeSort(arr, 0, arr.length - 1)
console.log(arr)

归并排序的优化方法

小数组优化：当子序列长度较小时，使用插入排序替代归并排序。

/**
 * 合并
 * @param {排序的数组} arr 
 * @param {最左边的下标} left 
 * @param {中间位置的下标} mid 
 * @param {最右边的下标} right 
 */
function merge(arr, left, mid, right) {

    // 阈值
    const THRESHOLD = 7;
    if (right - left <= THRESHOLD) {
        insertionSort(arr, left, right);
        return;
    }

    // 获取左边数组和右边数组得容量
    let n1 = mid - left + 1;
    let n2 = right - mid;


    // 按照mid 把数组分割到两个数组当中
    let leftArr = [];
    let rightArr = [];

    for (let i = 0; i < n1; i++) {
        const element = arr[i + left];
        leftArr.push(element)
    }
    for (let i = 0; i < n2; i++) {
        const element = arr[i + mid + 1];
        rightArr.push(element)
    }


    // 按照从小到大挑出来
    // i 是左边的数组读取的位置
    // j 是右边的数组读取的位置
    // k 是arr数组的位置
    let i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (leftArr[i] < rightArr[j]) {
            arr[k] = leftArr[i];
            i++
        }
        else {
            arr[k] = rightArr[j];
            j++
        }

        k++;
    }

    // 看左边右边的有没有排完
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// 插入排序
function insertionSort(arr, left, right) {
    for (let i = left + 1; i <= right; i++) {
        let currVal = arr[i];
        let j = i - 1;


        while (j >= 0 && arr[j] > currVal) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = currVal;
    }
}

/**
 * 排序
 * @param {排序的数组} arr 
 * @param {最左边的下标} left 
 * @param {最右边的下标} right 
 */
function mergeSort(arr, left, right) {
    if (left < right) {
        let mid = parseInt((right + left) / 2)
        mergeSort(arr, left, mid)
        mergeSort(arr, mid + 1, right)
        merge(arr, left, mid, right);
        //console.log("left: " + left + " mid: " + mid + " right: " + right)
    }
}


let arr = [12, 6, 13, 5, 14, 7, 122, 323, 1234, 54, 56, 54, 32, 1223, 3445, 1234];
mergeSort(arr, 0, arr.length - 1)
console.log(arr)