// This is a heapsort sample for TJS2 script engine.
// The original is at The Great Computer Language Shootout
// http://www.bagley.org/~doug/shootout/

var start = System.getTickCount();

var last = 42;

function
gen_random(max) {
    return( max * (last = (last * 3877 + 29573) % 139968) / 139968 );
}

function heapsort(n, ra) {
    var i, j;
    var ir = n;
    var l = (n >> 1) + 1;
    var rra;

    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;
		j++;
	    }
	}
	ra[i] = rra;
    }
}

{
	var ary = [];
	var N = 80000;
	for(var i = 1; i <= N; i++)
		ary[i] = gen_random(1);

	heapsort(N, ary);

}

System.inform(System.getTickCount() - start);

// 2002/1/3  (TJS1 script engine) 34290ms
// 2002/1/3  3095ms
// 2002/3/9  3065ms
// 2002/7/3  3044ms
