1 public class Solution {
 2     public void sortInteger(int[] a) {
 3         if (a == null || a.length == 0) {
 4             return;
 5         }
 6         int[] temp = new int[a.length];
 7         mergeDivideSort(a, 0, a.length - 1, temp);
 8     }
 9     public void mergeDivideSort(int[] a, int start, int end, int[] temp) {
10         //归并排序，不断分组直到分成单个数字
11         if (start >= end) {
12             return;
13         }
14         int mid = start + (end - start) / 2;
15         mergeSort(a, start, mid, temp);
16         mergeSort(a, mid + 1, end, temp);
17         merge(a, start, end, temp);
18     }
19     public void merge(int[] a, int start, int end, int[] temp) {
20         //将两个排序的组进行合并
21         int mid = start + (end - start) / 2;
22         int leftIndex = start;
23         int rightIndex = mid + 1;
24         int index = start;
25         while (leftIndex <= mid && rightIndex <= end) {
26             if (a[leftIndex] < a[rightIndex]) {
27                 temp[index++] = a[leftIndex++];
28             } else {
29                 temp[index++] = a[rightIndex++];
30             }
31         }
32         while (leftIndex <= mid) {
33             temp[index++] = a[leftIndex++];
34         }
35         while (rightIndex <= end) {
36             temp[index++] = a[rightIndex++];
37         }
38         //注意复制的时候从start到end
39         for (int i = start; i <= end; i++) {
40             a[i] = temp[i];
41         }
42     }
43 }