Timsort – the fastest sorting algorithm you’ve never heard of

• CPython

  1,314 59,531 10.0 Python

  The Python programming language

  

CPython source code contains a separate documentation [1] for a detailed description and discussion for the algorithm. TimSort optimizes for the number of comparisons (which are expensive in Python since each comparison can call a Python function) so all numbers are given by the number of comparisons.

[1] https://github.com/python/cpython/blob/main/Objects/listsort...

• pdqsort

  9 2,283 0.0 C++

  Pattern-defeating quicksort.

Closely related is pattern defeating quicksort ( https://github.com/orlp/pdqsort ), which adapts quicksort to take advantage of sorted runs. I've adapted a few quicksorts to pdqsort and seen good speedups (as people were often sorting partially sorted data)

Basically: Timsort is to mergesort as pdqsort is to quicksort

• InfluxDB

  www.influxdata.com sponsored

  Power Real-Time Data Analytics at Scale. Get real-time insights from all types of time series data with InfluxDB. Ingest, query, and analyze billions of data points in real-time with unbounded cardinality.

  

Suggest a related project