实现底部

/* 来 自 n o w    j a v a  . c o m*/


class MergeBU {


  private static Comparable[] comparable;


  private static boolean less(Comparable v, Comparable w) {

    return v.compareTo(w) < 0;

  }


  public static boolean isSorted(Comparable[] a) {

    for (int i = 1; i < a.length; i++)

      if (less(a[i], a[i - 1]))

        return false;


    return true;

  }
  /**
  N o w  J a v a  . c o m
  **/


  private static void merge(Comparable[] a, int lo, int mid, int hi) {

    // copy the array

    for (int k = lo; k <= hi; k++)

      comparable[k] = a[k];


    int i = lo, j = mid + 1;


    for (int k = lo; k <= hi; k++) {

      if (i > mid)

        a[k] = comparable[j++];

      else if (j > hi)

        a[k] = comparable[i++];

      else if (less(comparable[j], comparable[i]))

        a[k] = comparable[j++];

      else

        a[k] = comparable[i++];

    }

  }


  public static void sort(Comparable[] a) {

    int N = a.length;

    comparable = new Comparable[N];


    for (int sz = 1; sz < N; sz = sz + sz)

      for (int lo = 0; lo < N - sz; lo += sz + sz)

        merge(a, lo, lo + sz + 1, Math.min(lo + sz + sz - 1, N - 1));

  }


  public static