归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
public static void mergeSort(int[] elements) { if(null == elements || 1 >= elements.length) { // do nothing } else { int[] temp = new int[elements.length]; sort(elements, 0, elements.length-1, temp); }}private static void sort(int[] elements,int left,int right,int[] temp) { if(left < right) { int mid = (left + right) >> 1; sort(elements, left, mid, temp); sort(elements, mid+1, right, temp); merge(elements,left,mid,right,temp); }}private static void merge(int[] elements, int left, int mid, int right, int[] temp) { System.out.println("left="+left+",right="+right+",mid="+mid); int l = left;// 左数组指针 int r = mid + 1;// 右数组指针 int t = 0;// 临时数组指针 while(l <=mid && r<=right) { if(elements[l] <= elements[r]) { temp[t++] = elements[l++]; } else { temp[t++] = elements[r++]; } } // 将左边剩余元素填充进temp中 while(l <= mid) { temp[t++] = elements[l++]; } // 将右边剩余元素填充进temp中 while(r <= right) { temp[t++] = elements[r++]; } t = 0; while(left <= right) { elements[left++] = temp[t++]; } System.out.println("elements="+Arrays.toString(elements)); System.out.println("------------------------------------------------");} 测试代码：
public static void main(String[] args) { int[] array = {82 ,31 ,29 ,71, 72, 42, 64, 5, 110}; mergeSort(array);} 结果：
left=0,right=1,mid=0elements=[31, 82, 29, 71, 72, 42, 64, 5, 110]------------------------------------------------left=0,right=2,mid=1elements=[29, 31, 82, 71, 72, 42, 64, 5, 110]------------------------------------------------left=3,right=4,mid=3elements=[29, 31, 82, 71, 72, 42, 64, 5, 110]------------------------------------------------left=0,right=4,mid=2elements=[29, 31, 71, 72, 82, 42, 64, 5, 110]------------------------------------------------left=5,right=6,mid=5elements=[29, 31, 71, 72, 82, 42, 64, 5, 110]------------------------------------------------left=7,right=8,mid=7elements=[29, 31, 71, 72, 82, 42, 64, 5, 110]------------------------------------------------left=5,right=8,mid=6elements=[29, 31, 71, 72, 82, 5, 42, 64, 110]------------------------------------------------left=0,right=8,mid=4elements=[5, 29, 31, 42, 64, 71, 72, 82, 110]------------------------------------------------
参考博客：https://www.cnblogs.com/chengxiao/p/6194356.html