JuliaLang/julia — pull request #1691 by kmsquire (2012-12-06 10:31:46+00:00)
Title: WIP: Added timsort, plus misc. sort updates

See https://groups.google.com/forum/?fromgroups=#!searchin/julia-dev/timsort/julia-dev/bgFzFVT403s/tm1oe7vIVWAJ and https://gist.github.com/4168004

`timsort!` is almost complete, and is only missing the function versions which permutes indices. Right now, it's in a separate file which is included in sort, simply because adding 500 lines to `sort.jl` didn't seem like a good idea.

In the original gist, there was some code generated in a loop, which I unrolled in this version because I didn't trust myself to get it right inside of a macro.

I'll retest performance once everything is ready.

Additional Miscellaneous updates:

* removed `_jl_` prefix from front of `*sort` function calls
* removed `_lt` suffix from function variants

As a result, the `*sort` functions: `quicksort!`, `mergesort!`, `insertionsort!`, and `timsort!` are available in Base (not exported), along with `*_r!` variants for reverse sorting, and `_by!` variants for sorting with a function, so they can be accessed with `Base.quicksort!()`, `Base.insertionsort_r!()`, etc.