归并排序是利用递归与分治技术将数据划分为越来越小的半子表，再对半子表排序，最后再用递归方法将排好序的半子表合并为越来越大的有序序列。 原理如下：对于一个给定的一组记录，首先将每两个长度为1的子序列进行归并，得到n/2个长度为2或者为1的有序子序列，，再将其两两归并，反复执行此过程，得到一个有序序列
public class TestMergeSort { public static void main(String[] args) { int[] nums = new int[]{3,1,4,1,6,2}; MergeSort(nums,0,nums.length-1); for(int num:nums){ System.out.print(num+" "); } } public static void MergeSort(int[] array,int p,int q){ if( p < q){ int r = ( p + q ) / 2; MergeSort(array,p,r); MergeSort(array,r+1,q); Merge(array,p,r,q); } } public static void Merge(int[] array,int p,int r,int q){ int n1 = r - p + 1; int n2 = q - r; int[] L = new int[n1]; int[] R = new int[n2]; int i , j, k; for(i = 0 , k = p;i<n1;i++,k++){ L[i] = array[k]; } for(i = 0 , k = r+1;i < n2 ; i++,k++){ R[i] = array[k]; } for(i=0,j=0,k=p; i < n1 && j < n2; k++){ if(L[i] < R [j]){ array[k] = L[i]; i++; }else{ array[k] = R[j]; j++; } } while(i < n1){ array[k] = L[i]; i++; k++; } while(j < n2){ array[k] = R[j]; j++; k++; } } }