import java.util.Arrays;
public class MergeSort {
public static void sort(int arr[]) {
if (arr == null || arr.length < 2) {
return;
}
mergesort(arr, 0, arr.length - 1);
}
public static void mergesort(int[] arr, int L, int R) {
if (R == L) {
return;
}
int mid = L + ((R - L) >> 1); // (L+R)/2
// 左半部分
mergesort(arr, L, mid);
// 右半部分
mergesort(arr, mid + 1, R);
// 合并数组
merge(arr, L, mid, R);
}
public static void merge(int[] arr, int L, int mid, int R) {
// 辅助数组
int help[] = new int[R - L + 1];
int i = 0;
// 两个标记指针
int p1 = L;
int p2 = mid + 1;
while (p1 <= mid && p2 <= R) {
help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
}
// 一边越界的情况(一边大或者小永远不会放入辅助数组中)
// 两种情况只会出现一次:p1或者p2指针越界
// p2越界则p1一定未动,需要放入数组中
while (p1 <= mid) {
help[i++] = arr[p1++];
}
// p1越界则p2一定未动,需要放入数组中
while (p2 <= R) {
help[i++] = arr[p2++];
}
// 把辅助数值拷贝会原数组
for (i = 0; i < help.length; i++) {
arr[L + i] = help[i];
}
}
public static void main(String[] args) {
int arr[] = { 1, 6, 9, 8, 5, 1, 3, 5 };
sort(arr);
System.out.println(Arrays.toString(arr));
}
}