Derrick567
12/4/2016 - 11:10 AM

MergeSort.java


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);
  }

 }
}