思路： 将存有较多数据的数组，拆分成两个数组，分别排序后，将有序的两个数组合并。合并前递归拆分的过程，直至只有一个元素后，逐级合并。
实现：
package com.test; /** * 归并排序 * @author xurongsheng * @date 2017年4月14日 上午11:22:25 * */ public class MergeSort { private long[] target;//待排序数据 public MergeSort(){ } public MergeSort(int maxLength){ target = new long[maxLength]; } public void setTargetValue(int index,long value){ target[index] = value; } public long getTargetValue(int index){ return target[index]; } public void display(){ System.out.print("A="); for (int i = 0; i < target.length; i++) { System.out.print(target[i]+" "); } System.out.println(" "); } /** * 归并排序 * 时间复杂度： O(nlogN) * @author xurongsheng * @date 2017年4月14日 下午3:32:10 */ public void mergeSort(){ long[] workSpace = new long[target.length]; recMergeSort(workSpace,0,target.length-1); } /** * 归并 * @author xurongsheng * @date 2017年4月14日 上午11:33:29 * @param workSpace * @param lowerBound * @param upperBound */ private void recMergeSort(long[] workSpace,int lowerBound,int upperBound){ if(lowerBound == upperBound){ //只有一个元素,无需排序 return; }else{ int mid = (lowerBound+upperBound)/2; //中间项 recMergeSort(workSpace,lowerBound,mid); //排序左侧项 recMergeSort(workSpace,mid+1,upperBound); //排序右侧项 merge(workSpace,lowerBound,mid+1,upperBound); } } /** * 合并两个有序数组 * @author xurongsheng * @date 2017年4月14日 下午2:12:16 * @param workSpace * @param lowPtr * @param highPtr * @param upperBound */ private void merge(long[] workSpace,int lowPtr,int highPtr,int upperBound){ int j = 0; // int lowerBound = lowPtr; int mid = highPtr - 1; int n = upperBound - lowerBound + 1; while(lowPtr <= mid && highPtr <= upperBound){ if(target[lowPtr] < target[highPtr]){ workSpace[j++] = target[lowPtr++]; }else{ workSpace[j++] = target[highPtr++]; } } while(lowPtr <= mid){ workSpace[j++] = target[lowPtr++]; } while(highPtr <= upperBound){ workSpace[j++] = target[highPtr++]; } for(j = 0; j 效率： 归并排序的时间复杂度为 O(n*logN) 最好、最坏、平均情况下都是O(n*logN) logN为以2为底N的对数 由于计算过程中需要一个长度为n的临时空间，故 空间复杂度为O(N)
