javaScript数据结构和算法--归并排序

归并排序是一种分治算法，分而治之，将原始数组拆分成最小粒度的数组（数组的长度是1），接着将这些小数组进行归并（merge）,直到成为一个排序好的大数组。

归并排序图解

归并排序代码实现：

function MergeSort() {

    const array = [];

    this.insert = function(item) {

        array.push(item)

    }

    this.toString = function() {

        return array.join()

    }

    this.mergeSort = function() {

        arr = mergeSortRec(array);

    }

    const mergeSortRec = function(arr) {

        let length = arr.length;

        if(length === 1) {

            return arr; //分到数组的最小粒度1时，就不再递归调用自身拆分数组，

        }

        const mid = Math.floor(length/2); //把数组拆分成左右两个数组

        const left = arr.slice(0, mid);

        const right = arr.slice(mid, length);

        return merge(mergeSortRec(left), mergeSortRec(right));

    }

    const merge = function(left, right) {

        const result = [];

        let il = 0,

            ir = 0;

        while(il < left.length && ir <right.length) {

            if(left[il] < right[ir]) {

                result.push(left[il++]);

            }else {

                result.push(right[ir++]);

            }

        }

        while(il < left.length) {

            result.push([left[il++]]);

        }

        while(ir < right.length) {

            result.push(right[ir++]);

        }

        return result;

    }

}

var arr = new MergeSort();

arr.insert(3);

arr.insert(13);

arr.insert(32);

arr.insert(23);

arr.insert(11);

arr.insert(8);

arr.insert(33);

arr.insert(28);

console.log(arr.toString()); // 3,13,32,23,11,8,33,28

arr.mergeSort();

console.log(arr.toString());