Boost logo

Boost :

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
benchmarking required).

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.

Matt Bentley

Boost list run by bdawes at, gregod at, cpdaniel at, john at