Thursday, October 22, 2015

MergeSort in Java

 public static void mergesort(int[] A) {
  int[] aux = new int[A.length];
  mergesort(A, aux, 0, A.length-1);
 }
 private static void mergesort(int[] A, int[] aux, int lo, int hi) {
  if (lo >= hi) return;
  int m = (lo+hi) / 2;
  mergesort(A, aux, lo, m);
  mergesort(A, aux, m+1, hi);
  merge(A, aux, lo, m, hi);
 }
 private static void merge(int[] A, int[] aux, int lo, int m, int hi) {
  int i = lo;
  int j = m+1;
  for (int k=lo; k <= hi; k++) {
   if (i > m) {
    aux[k] = A[j];
    j++;
   } else if (j > hi) {
    aux[k] = A[i];
    i++;
   } else if (A[j] < A[i]) {
    aux[k] = A[j];
    j++;
   } else {
    aux[k] = A[i];
    i++;
   }
  }
  for (int k=lo; k <= hi; k++) {
   A[k] = aux[k];
  }
 }


No comments:

Post a Comment