Author Topic: Timsort — the fastest sorting algorithm you’ve never heard of  (Read 1527 times)

Offline Protools5LEGuy

  • Global Moderator
  • Platinum Member (500+ Posts)
  • *****
  • Posts: 2257

Quote
Timsort: A very fast , O(n log n), stable sorting algorithm built for the real world — not constructed in academia.

Quote
Timsort is a sorting algorithm that is efficient for real-world data and not created in an academic laboratory. Tim Peters created Timsort for the Python programming language in 2001. Timsort first analyses the list it is trying to sort and then chooses an approach based on the analysis of the list.

https://skerritt.blog/timsort-the-fastest-sorting-algorithm-youve-never-heard-of/

Looking for MacOS 9.2.4

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 529
Re: Timsort — the fastest sorting algorithm you’ve never heard of
« Reply #1 on: December 02, 2019, 08:49:39 AM »
The idea of using runs is good, but then you merge lists of different length, which is not optimal. Insertion sort for lists of 64 elements is bad.

I'll measure it when I have time.

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 529
Re: Timsort — the fastest sorting algorithm you’ve never heard of
« Reply #2 on: December 06, 2019, 08:05:04 AM »
He claims that in the worst case it's still as fast as MergeSort. I don't think so. If all elements are in reverse order, then searching for runs is a waste of time and he still has to do the MergeSort.

He proposes other 'improvements' too, like if the first element of the first list sorts after the last element of the second list then he just concatenates the lists. He seems to forget how many comparisons this requires.

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 529
Re: Timsort — the fastest sorting algorithm you’ve never heard of
« Reply #3 on: December 12, 2019, 06:29:22 AM »
It sees descending runs and reverses them.

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 529
Re: Timsort — the fastest sorting algorithm you’ve never heard of
« Reply #4 on: December 12, 2019, 06:31:01 AM »
I wrote TimSort for OS 9. It's based on Google's code from 2009. For perfectly randomized sequences it's 41% slower than MergeSort. For ordered or almost ordered sequences it's up to 20 times faster than MergeSort.

There's a strange instruction:
Code: [Select]
while ((count1 | count2)<minGallop);What's the logic of that? It looks like an error.

I changed it into
Code: [Select]
while ((count1<minGallop) or (count2<minGallop));This is 1.4% slower.

Then I changed it into
Code: [Select]
while ((count1<minGallop) and (count2<minGallop));This is 1.9% slower.

What should I do?

Offline OS923

  • Platinum Member (500+ Posts)
  • *****
  • Posts: 529
Re: Timsort — the fastest sorting algorithm you’ve never heard of
« Reply #5 on: December 13, 2019, 08:49:18 AM »
According to the description of the algorithm it has to be
Code: [Select]
while ((count1 + count2)<minGallop);
This looks like a rather arbitrary decision and it doesn't make much difference.