News for hackers. Stuff that matters.
Re:Timsort, the Python sorting algorithm by gopalv on Tuesday October 08, 2019 @06:20PM (#21197917)
> The basic idea is to read records for a while, get some stats about the key distribution, and set up the buckets to get a roughly equal fraction of the observed keyspace

Hadoop Terasort does the same thing of sort, which is to start off with a partitioner doing a radix sort & then sort each part with a lower O number of comparisons (the Spark one actually does local sorts and then has the merge-sort part just fetch ranges after first pass), however those two work great when the key ranges are almost entirely unique with no big runs of identical keys and differing values.

The Timsort one however has an advantage when there are huge runs of identical values or almost sorted inputs, like when you have a time-series with the occasional out of order packet. The galloping mode in the algorithm neatly eats those ranges up very fast.

My favourite example to show sorting is data dependent is the tricolor sort example[1], which illustrates what happens when you have a large number of identical keys.

[1] - https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Th...

There are no comments on this comment yet.