/** 

 * 归并排序 

 * 简介:将两个（或两个以上）有序表合并成一个新的有序表 即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列 

 * 时间复杂度为O(nlogn) 

 * 稳定排序方式 

 * @param nums 待排序数组 

 * @return 输出有序数组 

 */  

public class MergeSort {





public static void main(String[] args) {

int a[] = { 0, 3, 6, 2, 4, 9, 7, 5, 8, 1 };

new MergeSort().sort(a, 0, a.length - 1);

System.out.println(Arrays.toString(a));

}





public void sort(int[] a, int left, int right) {

if (left < right) {

int mid = (left + right) / 2;

sort(a, left, mid);

sort(a, mid + 1, right);

merge(a, left, mid, right);

}

}





public void merge(int[] arr, int left, int mid, int right) {

int a[], b[], c[];

int n1, n2;

n1 = mid - left + 1;

n2 = right - mid;

a = new int[n1];

b = new int[n2];

c = new int[n1 + n2];





int i = 0, j = 0, k = 0;





for (i = 0; i < n1; i++) {

a[i] = arr[left + i];

}





for (i = 0; i < n2; i++) {

b[i] = arr[mid + 1 + i];

}

i = 0;

while (i < n1 && j < n2) {

if (a[i] < b[j]) {

c[k++] = a[i++];

} else {

c[k++] = b[j++];

}

}

while (i < n1) {

c[k++] = a[i++];

}

while (j < n2) {

c[k++] = b[j++];

}

for (i = 0; i < c.length; i++) {

arr[left + i] = c[i];

}

}



}

注：合并有序数列时分配临时数组，但是过多的new操作会非常费时。因此作了下小小的变化。只在MergeSort()中new一个临时数组。后面的操作都共用这一个临时数组。

[0, 3, 6, 2, 4, 9, 7, 5, 8, 1]

[0, 3, 6, 2, 4, 9, 7, 5, 8, 1]

[0, 3, 6, 2, 4, 9, 7, 5, 8, 1]

[0, 3, 6, 2, 4, 9, 7, 5, 8, 1]

[0, 2, 3, 4, 6, 9, 7, 5, 8, 1]

[0, 2, 3, 4, 6, 7, 9, 5, 8, 1]

[0, 2, 3, 4, 6, 5, 7, 9, 8, 1]

[0, 2, 3, 4, 6, 5, 7, 9, 1, 8]

[0, 2, 3, 4, 6, 1, 5, 7, 8, 9]

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]