//! Version of the quicksort sample from the eval README
//! with a couple of necessary type annotations.

sort = defer(|quick_sort: (_) -> [Num]| {
    |xs| {
        if(xs as [Num] == (), || () as [Num], || {
            (pivot, ...rest) = xs as any;
            lesser_part = rest.filter(|x| x < pivot).quick_sort();
            greater_part = rest.filter(|x| x >= pivot).quick_sort();
            lesser_part.push(pivot).merge(greater_part)
        })()
    }
});

assert_eq((1, 7, -3, 2, -1, 4, 2).sort(), (-3, -1, 1, 2, 2, 4, 7));

xs = array(1000, |_| rand_num(0, 100)).sort();
{ sorted } = xs.fold(
    #{ prev: -1, sorted: true },
    |{ prev, sorted }, x| #{
        prev: x,
        sorted: sorted && prev <= x
    },
);
assert(sorted);