归并排序

　　归并排序的思想为分治法，即将一个数组不断往下划分，直至为单一的元素，然后将两个元素进行合并。

　　俩个有序的数组合并的方法：假设现有a，b两个有序数组，各自起点分别为i=0,j=0，如果a[i]<b[j]，则将a[i++]放入新的一个数组中,否则取另一个b[j++]，继续与b[j]或者a[i]进行比较。这样即简单合并为一个有序数组。

　　而归并排序，首先实现的就是把数组规划。将数组不断划分，直至划分只有单个数，然后开始将最底层的两个数，即可以看作为两个有序的数组，进行归并。每归并一次，序列扩大，继续归并。

　　归并排序中的数组划分，用到的是递归的方式。

　　

import java.util.Arrays;
public class Merge {　　//将两个有序的序列合并成一个
    public void MergeSort(int first,int mid,int last,int[] A,int[] temp){　　　　
        int i=first,j=mid+1;
        int index=0;
        while(i<=mid && j<=last){
            if(A[i]>=A[j]){
                temp[index++]=A[j++];
            }
            else{
                temp[index++]=A[i++];
            }
        }
        while(j<=last){
            temp[index++]=A[j++];
        }
        while(i<=mid){
            temp[index++]=A[i++];
        }
        for(i=0;first+i<=last;i++){
            A[first+i]=temp[i];
        }
24     }
    public void MergeArray(int first,int last,int[] A,int[] temp){　　　　//数组划分
        int mid=(first+last)/2;
        if(first<last){
            MergeArray(first,mid,A,temp);    //左序列　　　　不断的递归调用自身，向下递归，直至first=last,即分为了单一的一个数


            MergeArray(mid+1,last,A,temp);    //右序列


            MergeSort(first,mid,last,A,temp);　　　//在递归到了最底层，然后开始把两个数字（看作为两个有序的序列）开始归并一个新的序列，然后向上执行新的归并
        }
    }
    Merge(int[] A,int n){　　　　//入口
        int[] temp=new int[n];
        MergeArray(0,n-1,A,temp);
    }
}

　　此归并排序的关键在与划分为单一的元素即最小有序序列后开始向上归并。