合并排序

javascript版本：

1. function merge(left, right){
   
2.  var result = [];
   
3.  while (left.length > 0 && right.length > 0){
   
4.   if (left[0] < right[0]){
   
5.     result.push(left.shift());//把最小的最先取出，放到结果集中
   
6.   } else {
   
7.     result.push(right.shift());
   
8.   }
   
9.  } return result.concat(left).concat(right);//剩下的就是合并，这样就排好序了
   
10. }
    
11. function mergeSort(array){
    
12.  if (array.length == 1) {
    
13.   return array;
    
14.  }
    
15.  var middle = Math.floor(array.length / 2),//求出中点
    
16.  left = array.slice(0, middle),//分割数组
    
17.  right = array.slice(middle);
    
18.  return merge(mergeSort(left), mergeSort(right));//递归合并与排序
    
19. }

ruby版本：

1. def merge(left, right)
   
2.  final = []
   
3.  until left.empty? or right.empty?
   
4.   final << ( left.first < right.first ? left.shift : right.shift )
   
5.  end
   
6.  final + left + right
   
7. end
   
8. def mergeSort(array)
   
9.  return array if array.size < 2
   
10.  left = array.first(array.size/2)
    
11.  right = array.last(array.size - array.size/2)
    
12.  merge(mergeSort(left), mergeSort(right))
    
13. end