归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而**治(conquer)**的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。

作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

在《数据结构与算法 JavaScript 描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However,itisnotpossibletodosoinJavaScript,astherecursiongoestoodeepforthelanguagetohandle.然而，在JavaScript中这种方式不太可行，因为这个算法的递归深度对它来讲太深了。

说实话，我不太理解这句话。意思是 JavaScript 编译器内存太小，递归太深容易造成内存溢出吗？还望有大神能够指教。

和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。

代码实现

实例

functionmergeSort(arr){//采用自上而下的递归方法varlen=arr.length;if(lenreturnarr;}varmiddle=Math.floor(len/2),left=arr.slice(0,middle),right=arr.slice(middle);returnmerge(mergeSort(left),mergeSort(right));}functionmerge(left,right){varresult=[];while(left.length&&right.length){if(left[0]else{result.push(right.shift());}}while(left.length)result.push(left.shift());while(right.length)result.push(right.shift());returnresult;}Python

实例

defmergeSort(arr):importmathif(len(arr)returnarrmiddle=math.floor(len(arr)/2)left,right=arr[0:middle],arr[middle:]returnmerge(mergeSort(left),mergeSort(right))defmerge(left,right):result=[]whileleftandright:ifleft[0]else:result.append(right.pop(0));whileleft:result.append(left.pop(0))whileright:result.append(right.pop(0));returnresultGo

实例

funcmergeSort(arr[]int)[]int{length:=len(arr)iflengthreturnarr}middle:=length/2left:=arr[0:middle]right:=arr[middle:]returnmerge(mergeSort(left),mergeSort(right))}funcmerge(left[]int,right[]int)[]int{varresult[]intforlen(left)!=0&&len(right)!=0{ifleft[0]else{result=append(result,right[0])right=right[1:]}}forlen(left)!=0{result=append(result,left[0])left=left[1:]}forlen(right)!=0{result=append(result,right[0])right=right[1:]}returnresult}Java

实例

publicclassMergeSortimplementsIArraySort{@Overridepublicint[]sort(int[]sourceArray)throwsException{//对arr进行拷贝，不改变参数内容int[]arr=Arrays.copyOf(sourceArray,sourceArray.length);if(arr.lengthreturnarr;}intmiddle=(int)Math.floor(arr.length/2);int[]left=Arrays.copyOfRange(arr,0,middle);int[]right=Arrays.copyOfRange(arr,middle,arr.length);returnmerge(sort(left),sort(right));}protectedint[]merge(int[]left,int[]right){int[]result=newint[left.length+right.length];inti=0;while(left.length>0&&right.length>0){if(left[0]else{result[i++]=right[0];right=Arrays.copyOfRange(right,1,right.length);}}while(left.length>0){result[i++]=left[0];left=Arrays.copyOfRange(left,1,left.length);}while(right.length>0){result[i++]=right[0];right=Arrays.copyOfRange(right,1,right.length);}returnresult;}}PHP

实例

functionmergeSort($arr){$len=count($arr);if($lenreturn$arr;}$middle=floor($len/2);$left=array_slice($arr,0,$middle);$right=array_slice($arr,$middle);returnmerge(mergeSort($left),mergeSort($right));}functionmerge($left,$right){$result=[];while(count($left)>0&&count($right)>0){if($left[0]$right[0]){$result[]=array_shift($left);}else{$result[]=array_shift($right);}}while(count($left))$result[]=array_shift($left);while(count($right))$result[]=array_shift($right);return$result;}

C

实例

intmin(intx,inty){returnxfor(seg=1;segfor(start=0;startwhile(start1while(start1while(start2if(a!=arr){inti;for(i=0;i

递归版：

实例

voidmerge_sort_recursive(intarr[],intreg[],intstart,intend){if(start>=end)return;intlen=end-start,mid=(len>>1)+start;intstart1=start,end1=mid;intstart2=mid+1,end2=end;merge_sort_recursive(arr,reg,start1,end1);merge_sort_recursive(arr,reg,start2,end2);intk=start;while(start1while(start1while(start2for(k=start;kC++

迭代版：

实例

template//整數或浮點數皆可使用,若要使用物件(class)時必須設定"小於"(for(intseg=1;segfor(intstart=0;startwhile(start1while(start1while(start2if(a!=arr){for(inti=0;i

递归版：

实例

voidMerge(vector&Array,intfront,intmid,intend){//preconditions://Array[front...mid]issorted//Array[mid+1...end]issorted//CopyArray[front...mid]toLeftSubArray//CopyArray[mid+1...end]toRightSubArrayvectorLeftSubArray(Array.begin()+front,Array.begin()+mid+1);vectorRightSubArray(Array.begin()+mid+1,Array.begin()+end+1);intidxLeft=0,idxRight=0;LeftSubArray.insert(LeftSubArray.end(),numeric_limits::max());RightSubArray.insert(RightSubArray.end(),numeric_limits::max());//PickminofLeftSubArray[idxLeft]andRightSubArray[idxRight],andputintoArray[i]for(inti=front;iif(LeftSubArray[idxLeft]else{Array[i]=RightSubArray[idxRight];idxRight++;}}}voidMergeSort(vector&Array,intfront,intend){if(front>=end)return;intmid=(front+end)/2;MergeSort(Array,front,mid);MergeSort(Array,mid+1,end);Merge(Array,front,mid,end);}C#

实例

publicstaticListsort(Listlst){if(lst.Countreturnlst;intmid=lst.Count/2;Listleft=newList();//定义左侧ListListright=newList();//定义右侧List//以下兩個循環把lst分為左右兩個Listfor(inti=0;ifor(intj=mid;jreturnmerge(left,right);}//////合併兩個已經排好序的List//////左側List///右側List///staticListmerge(Listleft,Listright){Listtemp=newList();while(left.Count>0&&right.Count>0){if(left[0]else{temp.Add(right[0]);right.RemoveAt(0);}}if(left.Count>0){for(inti=0;iif(right.Count>0){for(inti=0;ireturntemp;}Ruby

实例

defmergelistreturnlistiflist.size#Mergelambda{|left,right|final=[]untilleft.empty?orright.empty?finalifleft.firstelseright.shiftendendfinal+left+right}.callmerge(list[0...pivot]),merge(list[pivot..-1])end