合併排序是建立在归併操作上的一种有效的排序算法。该算法是採用分治法（Divide and Conquer）的一个非常典型的套用。
合併排序法是将两个（或两个以上）有序表合併成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合併为整体有序序列。
将已有序的子序列合併，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合併成一个有序表，称为2-路归併。合併排序也叫归併排序。
基本介绍
- 中文名：合併排序
- 特点：建立在归併操作上
- 属性：有效的排序算法
- 方法：分治法
基本概念
複杂度
最坏时间複杂度
最好时间複杂度
空间複杂度
与快速排序类似
实现
JAVA
public static void mergeSort(int[]array){ int length=array.length; int middle=length/2; if(length>1){ int[]left=Arrays.copyOfRange(array,0,middle);//拷贝数组array的左半部分 int[]right=Arrays.copyOfRange(array,middle,length);//拷贝数组array的右半部分 mergeSort(left);//递归array的左半部分 mergeSort(right);//递归array的右半部分 merge(array,left,right);//数组左半部分、右半部分合併到Array }}//合併数组，升序private static void merge(int[]result,int[]left,int[]right){ int i=0,l=0,r=0; while(l<left.length&&r<right.length){ if(left[l]<right[r]){ result[i]=left[l]; i++; l++; }else{ result[i]=right[r]; i++; r++; } } while(r<right.length){//如果右边剩下合併右边的 result[i]=right[r]; r++; i++; } while(l<left.length){ result[i]=left[l]; l++; i++; }}C/C++语言
程式1
/****************************//*author:不辞远*//****************************/#include <malloc.h>#include <stdlib.h>void mergesort(int*a,intlength){ int step; int*p,*q,*t; inti,j,k,len1,len2; int*temp; step=1; p=a; q=(int*)malloc(sizeof(int)*length); temp=q; while(step<length){ i=0; j=i+step; k=i; len1=i+step<length?i+step:length; len2=j+step<length?j+step:length; while(i<length){ while(i<len1&&j<len2){ q[k++]=p[i]<p[j]?p[i++]:p[j++]; } while(i<len1){ q[k++]=p[i++]; } while(j<len2){ q[k++]=p[j++]; } i=j; j=i+step; k=i; len1=i+step<length?i+step:length; len2=j+step<length?j+step:length; } step*=2; t=p; p=q; q=t; } if(a!=p){ memcpy(a,p,sizeof(int)*length); } free(temp);}void main(void){int arrary[]={9,6,1,3,8,4,2,0,5,7};mergesort(arrary,10);}程式2
排序位于[begin, end)中的整数
void sort(int*begin,int*end){int size=end-begin;int*p,*p1,*p2,*mid=begin+size/2;if(size<=1)return;//边界条件sort(begin,mid);//递归求解sort(mid,end);p=(int*)malloc(size*sizeof(int));//申请临时空间for(p1=begin,p2=mid;p1!=mid||p2!=end;)//合併有序表*p++=(p2==end||p1!=mid&&*p1<*p2)?(*p1++):(*p2++);for(p-=size;begin!=end;)//回填*begin++=*p++;free(p-size);//释放临时空间}程式3
//C++#include<string>#include<iostream>using namespace std;//合併排序//合併两部分有序数组time:O(n)template<typename T>void Merge(T *arry,int start,int p,int end){ int lsize=p-start,rsize=end-p;//两个数组的大小 T * l=new T[lsize],*r=new T[rsize];//要合併的两个数组 memcpy(l,arry + start,sizeof(T)*lsize); memcpy(r,arry + p,sizeof(T)*rsize);//将要合併的数组複製 int lnow=0,rnow=0,i;//未合併的数字的位置 for(i=0;lnow<lsize&&rnow<rsize;i++) { if(l[lnow]>r[rnow])//取较大的数 { arry[start+i]=l[lnow]; lnow++; } else { arry[start+i]=r[rnow]; rnow++; } } if(lnow==lsize&&rnow!=rsize)//其中一个数组合併完以后，複製剩下的数据 { memcpy(arry+start+i,r+rnow,sizeof(T)*(rsize-rnow)); } else if(rnow==rsize&&lnow!=lsize) { memcpy(arry+start+i,l+lnow,sizeof(T)*(lsize-lnow)); } delete l; delete r;//清理记忆体 //return ;}//排序函式time:O(nlgn)template<typename T>void MergeSort(T *arry,int start,int end){ if(end-start > 1)//当元素个数为1时直接返回 { int p=(start + end)/2;//切割数组 MergeSort(arry,start,p); MergeSort(arry,p,end);//分别排序 Merge(arry,start,p,end);//合併数组 }}int main(){ int arr[10]={7,3,4,7,10,9,1,5,3,7}; MergeSort(arr,0,10); for(int i=0;i<10;i++) { cout<<arr[i]<<" "<<endl; } return 0;}
