java/test/Programs/SingleSource/UnitTests/heapsort.java

public class heapsort {

    public static final long IM = 139968;
    public static final long IA =   3877;
    public static final long IC =  29573;

    public static void main(String args[]) {
        int N = 100000;
        double []ary = new double[N+1];
        for (int i=1; i<=N; i++) {
            ary[i] = gen_random(1);
        }
        heapsort(N, ary);
        Test.println(ary[N]);
    }

    public static long last = 42;
    public static double gen_random(double max) {
        return( max * (last = (last * IA + IC) % IM) / IM );
    }

    public static void heapsort(int n, double ra[]) {
        int l, j, ir, i;
        double rra;

        l = (n >> 1) + 1;
        ir = n;
        for (;;) {
            if (l > 1) {
                rra = ra[--l];
            } else {
                rra = ra[ir];
                ra[ir] = ra[1];
                if (--ir == 1) {
                    ra[1] = rra;
                    return;
                }
            }
            i = l;
            j = l << 1;
            while (j <= ir) {
                if (j < ir && ra[j] < ra[j+1]) { ++j; }
                if (rra < ra[j]) {
                    ra[i] = ra[j];
                    j += (i = j);
                } else {
                    j = ir + 1;
                }
            }
            ra[i] = rra;
        }
    }
}