1 package Sort; 2  3 import org.junit.Test; 4  5 public class MergeSort { 6  7     // 归并排序 8     public void mergeSort(int[] array) { 9         divide(array, 0, array.length - 1);10     }11 12     // 1,划分13     public void divide(int[] array, int start, int end) {14 15         if (start < end) {16             int middle = (end + start) / 2;17             divide(array, start, middle);18             divide(array, middle + 1, end);19             merge(array, start, middle, end);20         }21     }22 23     // 2,归并24     public void merge(int[] array, int start, int middle, int end) {25 26         // a,定义两个子数组27         int[] left = null;28         int[] right = null;29         if (start > middle || middle + 1 > end)30             return;31         left = new int[middle - start + 1];32         right = new int[end - middle];33         34         // b,对两个子数组进行赋值35         for (int i = start; i <= middle; ++i)36             left[i - start] = array[i];37         for (int i = middle + 1; i <= end; ++i)38             right[i - middle - 1] = array[i];39 40         // c,对两个子数组进行归并41         int indexOfLeft = 0, indexOfRight = 0;42         int k = start;43         while (k <= end) {44             if (indexOfLeft < middle - start + 1 && indexOfRight < end - middle) {45                 if (left[indexOfLeft] < right[indexOfRight])46                     array[k++] = left[indexOfLeft++];47                 else48                     array[k++] = right[indexOfRight++];49             } else{50                 break;51             }52         }53         // 左半部分的数组已经拷贝完毕54         if (indexOfLeft == middle - start + 1 && indexOfRight < end - middle)55             while (indexOfRight < end - middle)56                 array[k++] = right[indexOfRight++];57         // 右半部分的数组已经拷贝完毕58         if (indexOfRight == end - middle && indexOfLeft < middle - start + 1)59             while (indexOfLeft < middle - start + 1)60                 array[k++] = left[indexOfLeft++];61     }62 63     @Test64     public void test() {65         int[] array = { 8, 2, 4, 9, 3, 6, 0 };66         mergeSort(array);67         Array.print(array);68     }69 }