归并排序

function mergeSort(items){
　　if (items.length == 1) {
　　return items;
　　}
　　var work = [];
　　for (var i=0, len=items.length; i < len; i++){
　　work.push([items[i]]);
　　}
　　work.push([]); //in case of odd number of items
　　for (var lim=len; lim > 1; lim = (lim+1)/2){
　　for (var j=0,k=0; k < lim; j++, k+=2){
　　work[j] = merge(work[k], work[k+1]);
　　}
　　work[j] = []; //in case of odd number of items
　　}
　　return work[0];
}

function merge(left, right){
　　var result = [];
　　while (left.length > 0 && right.length > 0){
　　if (left[0] < right[0]){
　　result.push(left.shift());
　　} else {
　　result.push(right.shift());
　　}
}
　　return result.concat(left).concat(right);
}

没用递归不存在栈溢出问题

归并排序

原文：https://www.cnblogs.com/CoderZX/p/11131625.html