Generate a fast sort function for small n, based on http://blog.racket-lang.org/2012/08/fully-inlined-merge-sort.html

sortk.jl

# Generate sort$n(vs), sortk(n1,...,nk) functions
function gen_sort(n)
    # Generate n symbols to manipulate
    vs = [gensym("v") for i=1:n]
    
    ## These two lines are setup for the sort$n functions

    # Set each symbol equal to an element of the input list
    vss = {:($v = vs[$i]) for (v,i) in enumerate(vs)}
    # Call the sort function
    push(vss, :(sortk($(vs...))))

    # Create teh sort$n(), sortk() functions
    quote
        function $(symbol("sort$n"))(vs)
            $(expr(:block, vss))
        end
        function sortk($(vs...))
            $(sort_k(vs, vs -> :[$(vs...)]))
        end
    end
end

# Merge consecutive sorted blocks together
function merge_k(as, bs, k)
    if length(as) == 0
        k(bs)
    elseif length(bs) == 0
        k(as)
    else
        a = as[1]
        b = bs[1]
        quote
            if $a <= $b
                $(merge_k(as[2:end], bs, vs -> k([a, vs...])))
            else                
                $(merge_k(as, bs[2:end], vs -> k([b, vs...])))
            end
        end
    end
end

# Sort a list
function sort_k(vs, k)
    if length(vs) < 2
        k(vs)
    else
        lvs = vs[1:int(end/2)]
        rvs = vs[int(end/2)+1:end]
        sort_k(lvs, 
               lvs -> sort_k(rvs,
                             rvs -> merge_k(lvs, rvs, k)))
    end
end