JuliaLang/julia — pull request #2151 by kmsquire (2013-01-28 18:51:52+00:00)
Title: Stablize TimSort

* Changed [r]gallop_last to return last element in array v <= x
to be consistent with searchsortedlast
* Fixed merge comparisons to be stable

```julia
julia> v = [6,5,2,2,2,5,10,8,7,6,2,1,6,3,7,9,4,3,2,10,2,2,8,8,8,2,2,2,2,7,3,9,9,6,9,8,1,10,10,5,9,7,8,6,1,4,7,5,1,7,1,6,3,10,9,6,6,8,3,3,2,9,8,9,2,3,9,9,9,6,6,2,8,9,10,6,10,4,7,10,9,6,5,10,6,2,3,1,10,9,5,10,2,6,3,5,9,9,6,3];

julia> p = sortperm(Sort.TimSort,v);

julia> s = v[p];

julia> [ issorted(p[s.==i]) for i=1:10 ]
10-element Any Array:
true
true
true
true
true
true
true
true
true
true

julia> all([issorted(sort(TimSort, Sort.By(a -> a[1]), [(el,i) for (i,el) in enumerate(rand(1:4, 1025))])) for i = 1:1000])
true
```