JavaScript——归并排序

//归并排序
    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());
            }
        }
        return result.concat(left).concat(right);

    }

    function mergeSort(arr) {
        if (arr.length == 1) {
            return arr;
        }
        let mid = Math.floor(arr.length / 2);
        let left = arr.slice(0, mid);
        let right = arr.slice(mid);

        return merge(mergeSort(left), mergeSort(right));
    }
    document.write(mergeSort([1, 2, 3, 4, 5, 6, 7, 8, 9]));
           

使用循环可以得到一个迭代实现的算法，代码如下

function mergeSort(items) {
        if (items.length == 1)
            return items;
        let work = [];
        for (var i = 0; i < items.length; i++) {
            work.push(items[i]);
        }
        work.push([]);
        for (var l = items.length; l > 1; l = (l + 1) / 2) {
            for (var j = 0, k = 0; k < l; j++, k += 2) {
                work[j] = merge(work[k], work[k + 1]);
            }
            work[j] = [];
        }
        return work[0];
    }
    document.write(mergeSort([1, 2, 3, 4, 5, 6, 7, 8, 1]));