Re: [boost] [sort] Timsort review reminder

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:
https://github.com/gfx/cpp-TimSort/

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