def partition(f, arr)
    return [[], []] if arr.empty?
    x, *xs = arr
    ys, zs = partition(f, xs)
    return [[x, *ys], zs] if f[x]
    [ys, [x, *zs]]
end

def qsort(arr)
    return arr if arr.empty?
    p, *xs = arr
    ys, zs = partition(->(x){x <= p}, xs)
    [*qsort(ys), p, *qsort(zs)]
end

arr = [1,3,2,5,4,6]
p partition(:odd?, arr)  
p qsort(arr)