归并排序

• 时间复杂度： O(nlogN)
• 空间复杂度： O(n)

// var initArr = [9,8,7,6,5,4,3,2, 12,20,40];

// 归并排序
function mergeSort(arr) {
    var len = arr.length;
    _mergeSort(arr, 0, len - 1)
}

function _mergeSort(arr, left, right)  {
    if (left >= right) {
        return;
    }
    // debugger;
    
    var mid = parseInt((left + right) / 2);

    // console.log('left', left, 'right', right)
    _mergeSort(arr, left, mid);
    _mergeSort(arr, mid + 1, right);
    _merge(arr, left, mid, right);
}

function _merge(arr, left, mid,right) {
    
    // console.log('')

    var tempArr = [];
    var leftPoint = left;
    var rightPoint = mid + 1;

    // if (arr[leftPoint] < arr[rightPoint]) {
    //     leftPoint ++;
    // } else {
    //     rightPoint ++;
    // }
    
    // 循环为 merge的总长度
    for(var i = 0; i < right - left + 1; i ++) {
        // debugger;
        if (leftPoint > mid) {
            tempArr.push(arr[rightPoint]);
            rightPoint ++;
            continue;
        }

        if (rightPoint > right) {
            tempArr.push(arr[leftPoint]);
            leftPoint ++;
            continue;
        }

        if (arr[leftPoint] < arr[rightPoint]) {
            tempArr.push(arr[leftPoint]);
            leftPoint ++;
            continue;
        } else {
            tempArr.push(arr[rightPoint]);
            rightPoint ++;
            continue;
        }
    }

    tempArr.forEach((val, index) => {
        // console.log(i, value)
        arr[left + index] = val;
    });
    // debugger;

    // console.log(tempArr)
}

console.time('优化后');
mergeSort(window.testArr);
console.timeEnd('优化后');
// console.log(testArr)

// console.log(initArr)