归并排序是一种分治算法，分而治之，将原始数组拆分成最小粒度的数组（数组的长度是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());
