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

81–90 of 135 posts

Re: Timsort, the Python sorting algorithm

#81

Post by pgwhalen »

eropple wrote: post #45
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.

Understanding where a system breaks is a pretty critical part of "producing good working code," at least for definitions of "good" beyond "closes the bite-sized, cog-in-a-machine story assigned to me in this sprint." I'd hope that any developer making decisions of note in a nontrivial system was at least dimly aware of their language's sort complexity.

How often are you sorting something where N is great enough for it to matter how the sorting works? I spend most of my time choosing data structures such that sorting anything other than handful of elements is unnecessary.

Re: Timsort, the Python sorting algorithm

#82

Post by longemen3000 »

AnimalMuppet wrote: post #57
naniwaduni wrote: post #52

Earlier quoted context omitted.

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

maybe you shouldn't supply invalid comparisons in the first place. but if you do, crashing seems like an appropriate response

Re: Timsort, the Python sorting algorithm

#83

Post by unnouinceput »

zitterbewegung wrote: post #56
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 .

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 the following "Grover iteration" r(N) times. Iteration? That means one state of the computation is waiting for a previous one to be completed. That, to me, sounds like not a true parallelization algorithm, hence randomsort still wins.

Re: Timsort, the Python sorting algorithm

#85

Post by wil421 »

AnimalMuppet wrote: post #57
naniwaduni wrote: post #52

Earlier quoted context omitted.

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

Crash so when wil421 sort is implemented in the next version I’m not scratching my head months or years later.

Re: Timsort, the Python sorting algorithm

#86

Post by thehappypm »

Animats wrote: post #24

You can beat O(n log n). That limit is for sorts that use only a ">" comparison. A distribution sort, where you distribute the keys over buckets, can approach O(n). The first software patent, for SyncSort, is for a sort that beats O(n log n). The basic idea is to read records for a while, get some stats about the key distribution, and set up the buckets to get a roughly equal fraction of the observed keyspace. If blo…

Counting sorts are super neat and O(n), if the number of unique items is really small.

Imagine a list of all 0s and 1s that you wanted to sort (like 001110101). Why bother sorting? Just count up how many 0’s and 1’s there are (four 0’s, five 1’s) and generate the sorted list. O(n).

Clearly this doesn’t work when you have real world data to sort, but it is the basis for a radix sort, where you sort a batch of numbers digit-by-digit, giving you O(n*d). Though I think it’s rarely used.

Re: Timsort, the Python sorting algorithm

#87

Post by kevingadd »

stefan_ wrote: post #26
ignoramous wrote: post #18

My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1]. [0] Some of the core JDK developers are really on another level. The JDK…

Then, many years later, input was found that made the Java version crash: https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...

I found a similar problem using a fairly battle-tested C# implementation of timsort. Felt lucky that I had managed to reproduce it in a dev environment instead of it being a mysterious crash for users.

Re: Timsort, the Python sorting algorithm

#88

Post by loeg »

joshuamorton wrote: post #79
loeg wrote: post #65

Earlier quoted context omitted.

GP is talking about radix sort, basically. If you know all your keys are integers you can sort in O(n log k) (k is maximal key width in bits).

You have a bit of a repetition here backwards. You can sort in O(n * k), where k is the maximal key width in bits. This ends up being O(n log(k)). Your formulation suggests radix sort running in O(n log(log(k))), which isn't quite true.

Sorry, my mistake -- you're totally right. Number of bits is log_2(k), where k is just the maximal key number.

Re: Timsort, the Python sorting algorithm

#89

Post by loeg »

vitus wrote: post #80
loeg wrote: post #64

Earlier quoted context omitted.

Python sort works on generic objects that probide ">=", not more specific types. For the generic algorithm, as I'm sure you're aware, O(n log n) is optimal. And yes, radix sorts are something like O(n log k), where k is the bitwidth of the maximal key. Since k is often a constant this could be thought of as O(n). A Python sort could enumerate the list, check for all (1) integer contents and (2) no overridden comparat…

nit: runtime for radix sort is O(nk), since you sort the full list by each of the digits, sequentially. I've always thought claiming radix sort on integers to be linear was a bit disingenuous, since k In fact, if your integers are all unique, then k >= log(n). (for consistent choice of base for log)

You're totally right. joshuamorton made the same correction on another comment where I made the same error. Mea culpa!
Post reply on HN