归并排序是高级排序算法中唯一稳定的排序算法，归并排序的主要思想是分治，通过把一个大问题划分成若干个小问题从而缩小问题的规模，通过这样不断地划分，最后问题能够很容易地解出来时就可以采用直接求解法解出来，最后合并各个解。
归并排序的时间复杂度是O(n*logn);
归并排序在降低时间复杂性的时候耗费了额外的空间；
归并排序在规模很小的时候时间都消耗在递归上了，当规模减小到一定程度后我们可以采用插入排序对其排序，这样就能使效率大大提高。
public class Main {
public static void main(String[] args) {
int[] a={1,5,2,8,9,0,4,5,5,66,66,77,33,435,56,76789,9,9,0};
a=mergeSort(a,0,a.length);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
return;
}
public static int[] mergeSort(int[] array,int head,int tail){
if(tail-head==1){
return new int[]{array[head]};
}
int mid = (head+tail)/2;
int[] a = mergeSort(array,head,mid);
int[] b = mergeSort(array,mid,tail);
int[] c = new int[a.length+b.length];
int i=0;
int j=0;
int k=0;
while(i<a.length&&j<b.length&&k<c.length){
if(a[i]>b[j]){
c[k++]=b[j++];
}else{
c[k++]=a[i++];
}
if(i==a.length){
while(j<b.length){
c[k++]=b[j++];
}
}
if(j==b.length){
while(i<a.length){
c[k++]=a[i++];
}
}
}
return c;
}
}
输出：
0 0 1 2 4 5 5 5 8 9 9 9 33 56 66 66 77 435 76789
改进后的归并排序：
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a={1,5,2,8,9,0,4,5,5,66,66,77,33,435,56,76789,9,9,0};
a=mergeSort(a,0,a.length);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
return;
}
public static int[] mergeSort(int[] array,int head,int tail){
if(tail-head<5){
return insertSort(array,head,tail);
}
int mid = (head+tail)/2;
int[] a = mergeSort(array,head,mid);
int[] b = mergeSort(array,mid,tail);
int[] c = new int[a.length+b.length];
int i=0;
int j=0;
int k=0;
while(i<a.length&&j<b.length&&k<c.length){
if(a[i]>b[j]){
c[k++]=b[j++];
}else{
c[k++]=a[i++];
}
if(i==a.length){
while(j<b.length){
c[k++]=b[j++];
}
}
if(j==b.length){
while(i<a.length){
c[k++]=a[i++];
}
}
}
return c;
}
public static int[] insertSort(int[]array,int head,int tail){
int n=tail-head;
int[] a=new int[n];
for(int i=0;i<n;i++){
int key=array[head+i];
int j=i;
while(j-1>=0&&a[j-1]>key){
a[j]=a[j-1];
j--;
}
a[j]=key;
}
return a;
}
}
输出：
0 0 1 2 4 5 5 5 8 9 9 9 33 56 66 66 77 435 76789
这个算法还有可改进之处：合并数组的时候可以用一个指针数组记录原数组的排序关系，这样就能够很高效地完成归并排序；
下面给出实现代码（link数组）:
这里需要注意的一点是:数组的下标如果是从0开始的话，link链表的尾就不能用0表示，下面代码中用-1表示了链表尾。
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] a={1,5,2,8,9,0,4,5,5,66,66,77,33,435,56,76789,9,9,0};
int[] link=new int[a.length];
for(int i=0;i<a.length;i++){
link[i]=-1;
}
int i=mergeSort(a,link,0,a.length);
while(i!=-1){
System.out.print(a[i]+" ");
i=link[i];
}
return;
}
public static int mergeSort(int[] array,int[] link,int head,int tail){
if(tail-head<=1){
link[head]=-1;
// System.out.print(head+" ");
return head;
}
int mid = (head+tail)/2;
int i = mergeSort(array,link,head,mid);
int j = mergeSort(array,link,mid,tail);
int q = -1;
if(array[i]>array[j]){
q=j;
j=link[j];
}else{
q=i;
i=link[i];
}
int p=q;
while(i!=-1&&j!=-1){
if(array[i]>array[j]){
link[p]=j;
p=j;
j=link[j];
}else{
link[p]=i;
p=i;
i=link[i];
}
}
if(i==-1){
link[p]=j;
}else{
link[p]=i;
}
return q;
}
}
输出：
0 0 1 2 4 5 5 5 8 9 9 9 33 56 66 66 77 435 76789