// IE Test: javac Batcher.java; appletviewer Batcher.html
import java.awt.*;
public class Batcher extends Animate
  {	
    static int N;
    void sort(double[] a, int l, int r)
      { N = (l+r)/2; mergesort(a, l, N-1); }
    void compexch(double [] a, int i, int j) 
      { if (less(a, j, i)) exch(a, i, j); }
    void shuffle(double a[], int l, int r)
      { int i, j, m = (l+r)/2;
        for (i = l, j = 0; i <= r; i+=2, j++)
          { exch(a, N+i, l+j); exch(a, N+i+1, m+1+j); }
        for (i = l; i <= r; i++) exch(a, i, N+i);
      }
    void unshuffle(double a[], int l, int r)
      { int i, j, m = (l+r)/2;
        for (i = l, j = 0; i <= r; i+=2, j++)
          { exch(a, N+l+j, i); exch(a, N+m+1+j, i+1); }
        for (i = l; i <= r; i++) exch(a, i, N+i);
      }
    void mergeTD(double a[], int l, int r)
      { int i, m = (l+r)/2;
        if (r == l+1) compexch(a, l, r);
        if (r < l+2) return;
        unshuffle(a, l, r);
        mergeTD(a, l, m); 
        mergeTD(a, m+1, r);
        shuffle(a, l, r);
        for (i = l+1; i < r; i+=2) 
          compexch(a, i, i+1);
      }
    void mergesort(double[] a, int l, int r)
      { int m = (r+l)/2;
        if (r <= l) return;
        mergesort(a, l, m);
        mergesort(a, m+1, r);
        mergeTD(a, l, r);
      }

  }