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

51–60 of 135 posts

Re: Timsort, the Python sorting algorithm

#51

Post by 1000units »

quickthrower2 wrote: post #39
boltzmannbrain wrote: post #21

"never heard of"?? I would hope all Python devs at some point Google "What algorithm is Python's built-in sort function?"... https://docs.python.org/2/howto/sorting.html#sort-stability-... https://stackoverflow.com/questions/10948920/what-algorithm-...

Great, yet another True-Scotsman of being a proper developer. There is so much you should have read, googled, written to be a "True" dev these days. My theory is - if you are often learning stuff and producing good working code be happy. Not every developer needs to know the underlying sort algorithms.

His point is a great many people are familiar with this algorithm by way of working with Python.

You can certainly be happy not knowing the tools of your trade very intimately, but that's definitely not something to encourage.

Re: Timsort, the Python sorting algorithm

#52

Post by naniwaduni »

ziggity wrote: post #49
jonas21 wrote: post #32

Earlier quoted context omitted.

The "Comparison method violates its general contract!" exception is due to a bug in the caller's code, not in the sort implementation. If you have a bug in your code, just because you're able to get away with it today doesn't mean you should expect to get away with it forever.

I agree in theory. But in practice that specific caller's code bug was so widespread and Timsort broke so much existing code that it warranted offering a "-Djava.util.Arrays.useLegacyMergeSort=true" option. The specific line from the Javadoc you're alluding to [0] is: > The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. The problem is the second implied half of that statement: Pr…

If you're willing to accept unsorted output from your sort function, why are you sorting? What are you sorting?

Re: Timsort, the Python sorting algorithm

#53

Post by paulddraper »

dkersten wrote: post #47
quickthrower2 wrote: post #39

Earlier quoted context omitted.

Great, yet another True-Scotsman of being a proper developer. There is so much you should have read, googled, written to be a "True" dev these days. My theory is - if you are often learning stuff and producing good working code be happy. Not every developer needs to know the underlying sort algorithms.

The person never said that you had to google it to be a "proper developer", just that they hoped that every python developer would have done so.

I hate to disappoint that hope but I have never search for Python's sorting algorithm.

Re: Timsort, the Python sorting algorithm

#54

Post by dang »

yagibear wrote: post #3

Never heard of since it was last discussed on HN: https://news.ycombinator.com/item?id=17436591

And https://news.ycombinator.com/item?id=17883461 after that.

Quite a few submissions for something no one has heard of: https://hn.algolia.com/?dateRange=all&page=0&prefix=true&que...

The other main discussions are 2011: https://news.ycombinator.com/item?id=3214527

2009: https://news.ycombinator.com/item?id=752677

Re: Timsort, the Python sorting algorithm

#55

Post by unnouinceput »

I, for one, cannot wait that quantum computing to be the norm, like current one is. Then the only algorithm everyone will use will be randomsort. Got a list to sort it? Allocate one q-bit for each element and apply randomsort and boom, done in under a picosecond, regardless of list size. This is the ultimate algorithm to be implemented for parallelization, all others will take more since they depend on sequence input.

Re: Timsort, the Python sorting algorithm

#56

Post by zitterbewegung »

unnouinceput wrote: post #55

I, for one, cannot wait that quantum computing to be the norm, like current one is. Then the only algorithm everyone will use will be randomsort. Got a list to sort it? Allocate one q-bit for each element and apply randomsort and boom, done in under a picosecond, regardless of list size. This is the ultimate algorithm to be implemented for parallelization, all others will take more since they depend on sequence input…

That’s not how it works . Grovers algorithm takes O(sqrt(n)) using a quantum computer .

Values in a quantum computer are superpositions but when measured they will return only one result. They don’t have an infinite amount of time and or space .

Re: Timsort, the Python sorting algorithm

#57

Post by AnimalMuppet »

naniwaduni wrote: post #52
ziggity wrote: post #49

Earlier quoted context omitted.

I agree in theory. But in practice that specific caller's code bug was so widespread and Timsort broke so much existing code that it warranted offering a "-Djava.util.Arrays.useLegacyMergeSort=true" option. The specific line from the Javadoc you're alluding to [0] is: > The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. The problem is the second implied half of that statement: Pr…

If you're willing to accept unsorted output from your sort function, why are you sorting? What are you sorting?

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.)

Re: Timsort, the Python sorting algorithm

#58

Post by hinkley »

z0r wrote: post #42
hinkley wrote: post #38

Earlier quoted context omitted.

I remember this article now. As someone else said, for certain time complexities there are more algorithms available. I believe when I realized that fixing my bug would turn it essentially into this algorithm, I found something else to do.

I just tried to read this, and not only is it horrifyingly complex it isn't stable, so it doesn't really fit the bill (even if you allow for strange complexities)

Aha! Thank you. That solves a mystery for me. Skimming it a few minutes ago, I thought it claimed to be stable, and I couldn't figure out why it didn't come to mind when I thought about merge sort.

If it's not stable, then what's the point? It's not a merge sort variant by the most important measure, IMO, and as I said, I was only considering merge sort variants.

Even with all of the additional logic people have created to avoid worst case performance, quicksort is simpler than this algorithm by a huge margin.

Re: Timsort, the Python sorting algorithm

#59

Post by billforsternz »

cdirkx wrote: post #35
billforsternz wrote: post #22

Earlier quoted context omitted.

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.

A "stable" sorting algorithm preserves the relative order of elements with "equal value". This doesn't really apply if you are only sorting simple values, as there is no difference between a 7 and another 7, but does if you are sorted more complicated objects by some key. Example: sorting 2#a, 1#c, 2#b by only the first number. An algorithm that produces 1#c, 2#b, 2#a is a correct sorting algorithm, but not stable as…

Thanks for the explanation, interesting.
Post reply on HN