js并归排序的思路

并归排序，就是分而治之，将长的数组分解为短的数组，一直分到最后，单个单个数组，我们就认为，只有一个元素的数组是有序的。然后再逐个的合并

1、拆分: 很容易

　　例如数组  [ 2,4,3,5,1,6,8,7 ];

　　先拆为  [2,4,3,5]  [1,6,8,7]

再拆    [2,4] [3,5]  [1,6] [8,7]

再拆  [2] [4] [3] [5] [1] [6] [8] [7]

最后，拆分的结果，每个子数组都是有序的

2、合并，具体怎么合并，可以先来考虑一下两个有序数组的合并

                var arrA = [1,3,6,8,20,40];

		var arrB = [2,5,9,10,15,26,30,50,100];

		//将任意两个有序的数组，合并为一个有序数组

		var i = 0,j=0,arrC = [];

		while(i < arrA.length && j < arrB.length){

			if(arrA[i] < arrB[j]){

				arrC.push(arrA[i]);

				i++;

			}else{

				arrC.push(arrB[j]);

				j++;

			}

		}

		while(i < arrA.length){

			arrC.push(arrA[i]);

			i++;

		}

		while(j < arrB.length){

			arrC.push(arrB[j]);

			j++;

		}

		console.log(arrC);

　　那么，我对于一个数组分段的时候，可以用 low mid high,分别表示，分段的起始点，中间点，结束点 ，，这三个点，可以得到两个有序数组，进行合并

采用递归拆分，拆分为单个元素之后，合并

		//对数组  arr,从 low-mid  和 mid-high 有序合并

		//相当于 arrA = arr[low:mid]; arrB = arr[mid:high]

		function merge(arr,low,mid,high){

			var list =  [];

			var i = low, j = mid+1;

			while(i <= mid && j <= high){

				if(arr[i]  <= arr[j]){

					list.push(arr[i++]);

				}else{

					list.push(arr[j++]);

				}

			}

			while( i <= mid){

				list.push(arr[i++]);

			}

			while(j <= high){

				list.push(arr[j++]);

			}

			var k = 0;

			for(i = low; i <= high; i++){ //将排序好的list，赋值给arr

				arr[i] = list[k++];

			}

		}

		var mergeSort = function(arr,low,high){  //递归拆分

			if(low < high){

				var mid = Math.floor((low + high)/2);

				mergeSort(arr,low,mid);

				mergeSort(arr,mid+1,high);

				merge(arr,low,mid,high);  //合并

			}

		}

		var list = [5,3,6,4,8,7,10,9,2];

		mergeSort(list,0,list.length-1);

		console.log(list);