On Sat, Nov 23, 2013 at 4:21 PM, Jeremy Harris <jgh@wizmail.org> wrote:
> Its performance shines on partially- or reverse-sorted input.
Search the archives for the work I did on timsort support a while
back. A patch was posted, that had some impressive results provided
you just considered the number of comparisons (and not TPS when
sorting text), but at the time my sense was that it didn't have broad
enough applicability for me to pursue further. That doesn't mean the
idea wasn't useful, and it certainly doesn't mean that my rough patch
couldn't be improved upon. For one thing, if there was a type that had
a comparator that was, say, an order of magnitude more expensive than
bttextcmp, it would definitely be a big win.
--
Peter Geoghegan