public class MergeSort {
public static void sort(int[] a, int low, int high) {
if (low >= high)
return;
int mid = (low + high) / 2;
sort(a, low, mid);
sort(a, mid+1, high);
merge(a, low, high, mid);
}
public static void merge(int[] a, int low, int high, int mid) {
if (low >= high)
return;
int[] tmp = new int[high - low + 1];
int l = low;
int r = mid+1;
int i = 0;
while (l <= mid && r <= high) {
if (a[l] < a[r]) {
tmp[i] = a[l];
l++;
}else {
tmp[i] = a[r];
r++;
}
i++;
}
while (l <= mid) {//左邊還有,全部加入
tmp[i] = a[l];
l++;
i++;
}
while (r <= high) {//右邊還有全部加入
tmp[i] = a[r];
r++;
i++;
}
for (int j = 0; j < tmp.length; j++) {
a[low + j] = tmp[j];
}
}
public static void main(String[] args) {
int[] arr = {22,5,3,3,4,9,2,8,3,0,1,5,6,11};
sort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
}