归并排序是是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。
算法思想
- 把 n 个元素看成 n 个长度为 l 的有序子表
- 进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表
- 重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。
举例分析
现有一数组：arr = [1,5,7,2,6,3,8,9]
当我使用归并排序的时候，首先将数组元素看成是长度为1的表，则：
[1] [5] [7] [2] [6] [3] [8] [9]
那么我们先两两合并，即合并为：
[1 , 5] [7 , 2] [6 , 3] [8 , 9]
| | | |
[1 , 5] [2 , 7] [3 , 6] [8 , 9]
那么我们继续进行两两表合并，即合并为：
[1 , 5 , 2 , 7] [3 , 6 , 8 , 9]
| |
[1 , 2 , 5 , 7] [3 , 6 , 8 , 9]
继续合并：
[1 , 2 , 5 , 7 , 3 , 6 , 8 , 9]
|
[1 , 2 , 3 , 5 , 6 , 7 , 8 , 9]
那么我们的归并排序就完成了
代码
function merge_sort(arr){
if(arr.length < 2){
return arr;
}
var middle = parseInt(arr.length/2);
var left = arr.slice(0,middle);
var right = arr.slice(middle);
return merge(merge_sort(left),merge_sort(right));
}
function merge(left,right){
var result = [];
var i = 0, j = 0;
while(i < left.length && j < right.length){
if(left[i] > right[j]){
result.push(right[j++]);
}
else{
result.push(left[i++]);
}
}
while(i < left.length){
result.push(left[i++]);
}
while(j < right.length){
result.push(right[j++]);
}
return result;
}
var arr = [1, 2, 3, 5, 6, 7, 8, 9];
var result = merge_sort(arr);
console.log(result); //[1, 2, 3, 5, 6, 7, 8, 9]
