// IE Test: javac MergeSortBU.java; appletviewer MergeSortBU.html
import java.awt.*;
public class MergeSortBU extends Animate
  {	
    static int N;
    void sort(double[] a, int l, int r)
      { N = (l+r)/2; mergesortBU(a, l, N-1); }
    void merge(double[] a, int l, int m, int r)
      { int i, j, k;
        for (i = m+1; i > l; i--) exch(a, N+i-1, i-1);
        for (j = m; j < r; j++) exch(a, N+r+m-j, j+1);
        for (k = l; k <= r; k++)
          if (less(a, N+i, N+j))
            exch(a, k, N+(i++)); else exch(a, k, N+(j--));
      }
    void mergesortBU(double[] a, int l, int r)
      { int i, m;
        for (m = 1; m < r-l; m = m+m)
          for (i = l; i <= r-m; i += m+m)
            if (i+m+m-1 < r)
              merge(a, i, i+m-1, i+m+m-1);
            else
              merge(a, i, i+m-1, r);
      }
  }