Subject: Re: [boost] [sort] Timsort review reminder
From: Soul Studios (matt_at_[hidden])
Date: 2017-06-11 01:05:47
Just some info for those who're unfamiliar with the algorithm:
As far as I understand it this particular implementation is based on
Fugi Goro's implementation here, which I have contributed to a little:
As the page will tell you, Timsort is faster for mostly-sorted or
reversed sequences, is stable as opposed to the bulk of std::sort
implementations which use quicksort variants, and in my experience is
also faster on random sequences where the range of values is low (more
As Niall has noted, it is O(n log n) in worst case scenario,
has a memory cost over quicksort/introsort/etc, and is generally slower
for more random sequences.
In some scenarios std::stable_sort is better, some worse.
Like Paul I see no reason for a review, just a headsup.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk