# -*- mode: icon -*-
# $Id: heapsort.icon,v 1.1 2001/05/08 02:46:59 doug Exp $
# http://www.bagley.org/~doug/shootout/

$define IM 139968
$define IA 3877
$define IC 29573

procedure gen_random(max)
    static LAST; initial LAST := 42;
    repeat { suspend((max * (LAST := (LAST * IA + IC) % IM)) / IM) }
end

procedure heapsort(n, ra)
    local l, j, ir, i, rra

    l := ishift(n, -1) + 1
    ir := n
    repeat {
        if (l > 1) then {
        l := l - 1
            rra := ra[l]
        } else {
            rra := ra[ir]
            ra[ir] := ra[1]
        ir := ir - 1
            if (ir == 1) then {
                ra[1] := rra
                return
            }
        }
        i := l
        j := ishift(l, 1)
        while (j <= ir) do {
            if ((j < ir) & (ra[j] < ra[j+1])) then {
        j := j + 1
        }
            if (rra < ra[j]) then {
                ra[i] := ra[j]
        i := j
                j := j + i
            } else {
                j := ir + 1
            }
        }
        ra[i] := rra
    }
end

procedure main(argv)
    n := argv[1] | 1
    ary := list(n)
    every i := 1 to n do ary[i] := gen_random(1.0)
    heapsort(n, ary)
    write(ary[n])
end