Timsort, the Python sorting algorithm

I heard of it from a talk about a bug in the implementation of TimSort in several popular libraries [1]. That bug should be fixed in Java, Android and Python.

If you're using another language, you might want to verify that the bug is fixed/not present in your library

[1] http://www.envisage-project.eu/proving-android-java-and-pyth...

Re: Timsort, the Python sorting algorithm

#5

Post by timothycrosley » Tue, Oct 08, 2019, 8:40 PM UTC

As an (unrelated to the Algorithm) Python developer, also named Tim, I've never been able to hear the last of it. Still a great algorithm, though!

Re: Timsort, the Python sorting algorithm

#6

Post by pwinnski » Tue, Oct 08, 2019, 8:54 PM UTC

I think most Python devs have heard of this, as well as avid followers of HN, of course.

Re: Timsort, the Python sorting algorithm

#7

Post by kbd » Tue, Oct 08, 2019, 8:59 PM UTC

saagarjha wrote: post #2

Note that Timsort uses O(n) extra space: sometimes this can be undesirable.

Note that this is true for any (edit: stable, nlogn) merge sort.

Re: Timsort, the Python sorting algorithm

#8

Post by ThreeFx » Tue, Oct 08, 2019, 9:03 PM UTC

kbd wrote: post #7

saagarjha wrote: post #2

Note that Timsort uses O(n) extra space: sometimes this can be undesirable.

Note that this is true for any (edit: stable, nlogn) merge sort.

Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.

Re: Timsort, the Python sorting algorithm

#9

Post by CraneWorm » Tue, Oct 08, 2019, 9:05 PM UTC

kbd wrote: post #7

saagarjha wrote: post #2

Note that Timsort uses O(n) extra space: sometimes this can be undesirable.

Note that this is true for any (edit: stable, nlogn) merge sort.

you can do merge sort in place

Re: Timsort, the Python sorting algorithm

#10

Post by beagle3 » Tue, Oct 08, 2019, 9:18 PM UTC

ThreeFx wrote: post #8

kbd wrote: post #7

Earlier quoted context omitted.

Note that this is true for any (edit: stable, nlogn) merge sort.

Not true in general, however IIRC it is the case if you want optimal (i.e. n log n) time complexity.

Not even in that case. Heapsort guarantees worst case n log n, and so does quicksort if you use an O(n) median selecting algorithm.

Stable sorts often do require that, (mergesort is usually stabble, heapsort and quicksort are inherently not), but even that's not required - there is a completely in-place variant of merge sort that only requires O(log n) space for stack (like quicksort; heapsort is O(1)). See e.g. https://xinok.wordpress.com/2014/08/17/in-place-merge-sort-d...