package cn.hcm;
public class MergeSort {
 /**
  * 合并两个有序数组
  * @param source
  * @param start
  * @param mid
  * @param end
  * @param sourceCopy
  */
 private static void merge(int[] source, int start, int mid, int end, int[] sourceCopy) {
  int midPlus = mid + 1; 
  int begin = start;
  
  int startTemp = start;
  int endTemp = end;
  
  while(true) {
   if(sourceCopy[start] < sourceCopy[midPlus]) {
    source[begin] = sourceCopy[start];
    begin++;
    start++;
    
    if(start > mid) {
     for(int i=midPlus; i<=end; i++) {
      source[begin] = sourceCopy[i];
      begin++;
     }
     break;
    }
   } else {
    source[begin] = sourceCopy[midPlus];
    begin++;
    midPlus++;
    
    if(midPlus > end) {
     for(int i=start; i<=mid; i++) {
      source[begin] = sourceCopy[i];
      begin++;
     }
     break;
    }
   }
  }
  
  for(int i=startTemp; i<=endTemp; i++) {
   sourceCopy[i] = source[i];
  }
 }
 
 
 /**
  * 归并排序
  * @param source
  * @param firstIndex
  * @param lastIndx
  * @param sourceCopy
  */
 private static void mergeSort(int[] source, int firstIndex, int lastIndx, int[] sourceCopy) {
  if(firstIndex < lastIndx) {
   int mid = (firstIndex + lastIndx)/2;
   mergeSort(source, firstIndex, mid, sourceCopy);
   mergeSort(source, mid+1, lastIndx, sourceCopy);
   merge(source, firstIndex, mid, lastIndx, sourceCopy);
  }
 }
 
 /**
  * 归并排序
  * @param source
  */
 public static int[] mergeSort(int[] source) {
  int[] sourceCopy = new int[source.length];
  for(int i=0; i<source.length; i++) {
   sourceCopy[i] = source[i];
  }
  mergeSort(source, 0, source.length-1, sourceCopy);
  return source;
 }
 
 public static void main(String[] args) {
  int[] source = new int[]{-67, -5,-4, 89, 77, 123, -1, -2, -89, 99, -1, 4,6,55,1};
  source = mergeSort(source);
  
  for(int i:source) {
   System.out.println(i);
  }
 }
 
}

归并排序