JavaScript-並べ替えアルゴリズム-並べ替え順序付け

特徴:

時間複雑度:O(nlog 2 n)

正規並べ替えは、安定した並べ替えアルゴリズム

である.
原理:(分割法)

原理は、2つの順序付きチェーンを連結する

と類似している.

は、複数の小さい順序行列に分割され、2つの連結によって最終的に完全なシーケンス

を実現する.
コードの実現:(再帰)

//            
function mergeSort(arr) {  
    const len = arr.length;
    if (len < 2) return arr;
    const middle = Math.floor(len >> 1);
    const left = arr.slice(0, middle);
    const right = arr.slice(middle);

    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
    let result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while (left.length) {
        result.push(left.shift());
    }
    while (right.length) {
        result.push(right.shift());
    }
    return result;
}