Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Timsort, the Python sorting algorithm

skerritt.blog

Post reply on HN
Print view View original

101–110 of 135 posts

Re: Timsort, the Python sorting algorithm

#101

Post by joshuamorton »

bloomer wrote: post #100
joshuamorton wrote: post #78

Earlier quoted context omitted.

No, radix sort is worst case O(n * k). In many common cases, k ~= log(n). IN certain specific cases, k < log(n), and specifically for cases where you have a very large n, but a bounded number of values (say, you're sorting 10 billion 4-bit ints), k can be considered a constant. But that is by no means generally true.

In most cases k << n. For 64-bit integers, byte wise radix sort k is 8, which is less than log n whenever n is more than 256. So, radix sort is typically much faster than an O(n log n) sort of your data support it. It just isn’t as widely used because it is not as general as a comparison based sort.

After a byte-wise radix sort you still have to sort within each bucket.

In the worst case, every element falls into a single bucket, at which point your best best is to do a bit wise radix sort over the low 8 bits.

This ends up being equivalent to k=log(n).

Re: Timsort, the Python sorting algorithm

#102

Post by unnouinceput »

saagarjha wrote: post #95
unnouinceput wrote: post #83

Earlier quoted context omitted.

We are today on quantum computing where we were in 18th century when Ada was creating the 1st computer program. Sure, Grover's algorithm is good for current state of quantum computing but when it will reach to be a current norm just like the Silicon based one is today then is entire state altogether. By that time Grover's algorithm will take it's place in history but will not be used in practice. From wiki: Perform t…

I suggest you read up on how superposition works in quantum computers–they not just computers with an infinite number of cores :/

No, they are not. Also 128 billion is a big enough number that if you'd say to a 18th century scientist who was working with punch cards computers that in the future one with 128 billion punch cards would exists he would've replied something along the lines, just like you, that there are not enough trees on Earth to create 128 billion cards for a single computer, let alone billion of them that they are more common than horses in 18th century. And yet, here we are, with computers that have 128 GB RAM, like the one I use to reply to you. So how about you let me dream big instead, eh?

Re: Timsort, the Python sorting algorithm

#103

Post by cbarrick »

leshow wrote: post #50
ken wrote: post #31

Besides Python and Java, it's also the sorting algorithm used by Chrome, Android, and Swift. At this point I think more than half the world's programmers are using Timsort, whether they realize it or not.

And Rust, the rust std lib uses a modified timsort/mergesort

FWIW, Rust uses Pattern-defeating quicksort for it's unstable sort.

[1] https://github.com/orlp/pdqsort [2] https://doc.rust-lang.org/std/vec/struct.Vec.html#method.sor...

Re: Timsort, the Python sorting algorithm

#105

Post by cbarrick »

hinkley wrote: post #43
anderskaseorg wrote: post #36

Earlier quoted context omitted.

Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 ( https://doi.org/10.1137/0206025 ). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.

It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array” Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage. Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but…

To be fair, tail calls don't require stack frames.

If it's just a matter of keeping up with the bounds of the partitions, I can see that being done in constant space.

Re: Timsort, the Python sorting algorithm

#106

Post by [deleted] »

kragen wrote: post #70
AnimalMuppet wrote: post #57

Earlier quoted context omitted.

If you supply an invalid comparison function to your sort function, which would you prefer to happen - that it crash, or that it give you unsorted output? (If you actually wanted sorted output, you should have provided a valid comparison function.)

Most of the time I want it to crash in development and give me unsorted output in production; debugging an unhandled exception is super easy compared to debugging sometimes incorrectly sorted output. In rare cases I would also want it to crash in production. I definitely don't want it to change between the two scenarios when I update my JVM.

[deleted]

Re: Timsort, the Python sorting algorithm

#107

Post by kbirkeland »

hinkley wrote: post #41
anderskaseorg wrote: post #36

Earlier quoted context omitted.

Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 ( https://doi.org/10.1137/0206025 ). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.

How many people do you suppose can read that link?

Google scholar returns a pdf[0] when searching the doi.

[0] https://epubs.siam.org/doi/pdf/10.1137/0206025

Re: Timsort, the Python sorting algorithm

#108

Post by gigatexal »

bloomer wrote: post #100
joshuamorton wrote: post #78

Earlier quoted context omitted.

No, radix sort is worst case O(n * k). In many common cases, k ~= log(n). IN certain specific cases, k < log(n), and specifically for cases where you have a very large n, but a bounded number of values (say, you're sorting 10 billion 4-bit ints), k can be considered a constant. But that is by no means generally true.

In most cases k << n. For 64-bit integers, byte wise radix sort k is 8, which is less than log n whenever n is more than 256. So, radix sort is typically much faster than an O(n log n) sort of your data support it. It just isn’t as widely used because it is not as general as a comparison based sort.

Jumping in this fascinating thread about sorting to ask what the double less than chevrons mean? I know what one means but what do two of them mean?

Re: Timsort, the Python sorting algorithm

#109

Post by anderskaseorg »

hinkley wrote: post #43
anderskaseorg wrote: post #36

Earlier quoted context omitted.

Algorithms for stable, in-place merging in linear time, hence merge sorting in O(n log n) time, have been known since 1977 ( https://doi.org/10.1137/0206025 ). This first algorithm was too complicated with too large of a constant factor to be practical, but has since been improved.

It concerns me that the most recent citation in that bibliography says “ We achieve our goal using Recursive Partitioning combined with In Place merging to sort a given array” Stack frames are external storage. I’d have to see the code to see how they manage to do recursion without log(n) external storage. Traditional merge sort can be written using iteration, which makes the external storage for sort state O(1), but…

The paper states that each merge operation uses a constant number of pointers. There’s no reason you couldn’t do an iterative merge sort with this in-place merge operation, just like you would with the standard merge operation, to sort with a constant number of pointers.

Re: Timsort, the Python sorting algorithm

#110

Post by hinkley »

billforsternz wrote: post #22
kbd wrote: post #7

Earlier quoted context omitted.

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

Heapsort is a lovely, simple, O(NlogN) sort that sorts in place (so that it requires no extra space). (Explicitly stating something that is implied by an existing response). Edit: Whoops, apparently heapsort is not "stable" (not sure what that means actually), sorry.

Said another way, if I sort my database by user names, the John Smith who has been my customer the longest always comes first in the line of John Smiths.

One of the things you can do with a stable sort is to fake complex sorting by iteratively sorting by each criteria. Though I have rarely seen that be practical anywhere other than tabular data.

Post reply on HN