package MergeSort;
public class MergeSort {
public static void main(String[] args) {
int arr[] = { 8, 7, 5, 4, 6, 3, 1, 2 ,50,33};
MergeSortM(arr, 0, arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
public static void Merge(int arr[], int p, int q, int r) {
int n1 = q - p + 1;
int n2 = r - q;
int L[] = new int[n1 + 1];
int R[] = new int[n2 + 1];
int i;
int j;
for (i = 0; i < n1; i++) {
L[i] = arr[p + i];
}
for (j = 0; j < n2; j++) {
R[j] = arr[q + j + 1];
}
L[n1] = Integer.MAX_VALUE;
R[n2] = Integer.MAX_VALUE;
i = 0;
j = 0;
for (int k = p; k <= r; k++) {
// //如果L取完R還沒取完就一直取R
// if(i>=L.length &&j<R.length){
// arr[k]=R[j];
// j++;
// }
// //如果R取完L還沒取完就一直取L
// if(j>=R.length &&i<L.length){
// arr[k]=L[i];
// i++;
// }
if (L[i] < R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
}
}
public static void MergeSortM(int arr[], int p, int r) {
if (p < r) {
int q = (p + r) / 2; // 3
MergeSortM(arr, p, q); // 0~3
MergeSortM(arr, q + 1, r);
Merge(arr, p, q, r);
}
}
}