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

Beating TimSort at Merging

earthly.dev

Post reply on HN
Print view View original

51–60 of 72 posts

Re: Beating TimSort at Merging

#51

Post by elpakal »

dang wrote: post #13

Past TimSort threads, for anyone interested: Timsort, the Python sorting algorithm - https://news.ycombinator.com/item?id=21196555 - Oct 2019 (131 comments) On the Worst-Case Complexity of TimSort - https://news.ycombinator.com/item?id=17883461 - Aug 2018 (74 comments) Timsort is a sorting algorithm that is efficient for real-world data - https://news.ycombinator.com/item?id=17436591 - July 2018 (77 comments) Functio…

Recently learned that Swift also uses TimSort, really cool to see other language implementations:

https://news.ycombinator.com/item?id=20884208

Re: Beating TimSort at Merging

#52

Post by adamgordonbell »

tim-peters wrote: post #47
adamgordonbell wrote: post #43

Earlier quoted context omitted.

Very Cool! Edit: Ok, I get it now. Don't just pop, binary search into it, so you can fast forward through. I'm not sure I'll get around to implementing that, at least not in the immediate future, but that makes total sense.

You already got a win - quit while you're ahead ;-) Note that plain binary search here is probably not a good idea. See "listsort.txt", in the same directory as "listobject.c", for excruciating details.

If I get it working, it can be TimMerge.

Re: Beating TimSort at Merging

#53

Post by saagarjha »

pg_bot wrote: post #49

I was thinking about how to make sorting faster the other day and was toying around with the idea of a permutation sort. If you think about a list of items generally (at least) one of the permutations of the list is guaranteed to be the correct sort order. Theoretically you should be able to do a binary search to find a correct permutation since there should always be a comparison you can do to reduce the search spac…

Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.

Re: Beating TimSort at Merging

#54

Post by tim-peters »

adamgordonbell wrote: post #52
tim-peters wrote: post #47

Earlier quoted context omitted.

You already got a win - quit while you're ahead ;-) Note that plain binary search here is probably not a good idea. See "listsort.txt", in the same directory as "listobject.c", for excruciating details.

If I get it working, it can be TimMerge.

Haha. AdamMerge works for me - I get enough abuse for naming a sort after myself ;-)

If you pursue this, you can probably throw out piles of the CPython code. That's trying to keep the result "in place", so has major code near-duplication to merge "into the left side" or "into the right side", to minimize the amount of temp memory needed (this depends on which input list is shorter).

But you're writing your output to a new list, so those cases are the same to you.

To keep the sort stable in all cases, though, you still need to distinguish between `gallop_left()` and `gallop_right()`.

Re: Beating TimSort at Merging

#55

Post by pg_bot »

saagarjha wrote: post #53
pg_bot wrote: post #49

I was thinking about how to make sorting faster the other day and was toying around with the idea of a permutation sort. If you think about a list of items generally (at least) one of the permutations of the list is guaranteed to be the correct sort order. Theoretically you should be able to do a binary search to find a correct permutation since there should always be a comparison you can do to reduce the search spac…

Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.

You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)

Re: Beating TimSort at Merging

#56

Post by saagarjha »

pg_bot wrote: post #55
saagarjha wrote: post #53

Earlier quoted context omitted.

Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.

You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)

No, I understand your algorithm, I’m just saying that you’ll start with n! permutations and halve that with each step. This will require log(n!) steps.

Re: Beating TimSort at Merging

#57

Post by tim-peters »

pg_bot wrote: post #55
saagarjha wrote: post #53

Earlier quoted context omitted.

Assuming constantly time comparison, the best you are going to be able to do is log(n!), which is O(n log n) by Stirling's approximation. But comparing a permutation is likely to be O(n), so you'll probably do worse than that.

You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)

Sorry, nope. There aren't n permutations you're searching through, but the factorial of n to search through. That's the heart of the information-theoretic proof that no comparison-based sorting algorithm can do better, on average, than needing a number of comparisons equal to the base-2 logarithm of the factorial of n. Which, as already said, is O(n log n).

Re: Beating TimSort at Merging

#58

Post by pg_bot »

tim-peters wrote: post #57
pg_bot wrote: post #55

Earlier quoted context omitted.

You don't need to compare permutations you reduce the set of possible permutations until you reach the one that must be the answer. Theoretical performance should be O(log n)

Sorry, nope. There aren't n permutations you're searching through, but the factorial of n to search through. That's the heart of the information-theoretic proof that no comparison-based sorting algorithm can do better, on average, than needing a number of comparisons equal to the base-2 logarithm of the factorial of n. Which, as already said, is O(n log n).

No, I understand that there are n! permutations. Again you aren't actually searching through the permutations. You're running comparisons on the data to reduce the set of possible permutations to the one it has to be. (pigeon hole principle) I believe my point still stands. You should be able to cut the search space in half with one comparison every single time, which should perform the same as a binary search.

Edit: You are correct I made a mistake in my big O notation, it should be O(n log n).

Re: Beating TimSort at Merging

#60

Post by j-pb »

tim-peters wrote: post #48
j-pb wrote: post #44

Earlier quoted context omitted.

Is there a reason to use galloping over an array vs a seek in a search tree? Better real world factors? Galloping, Demaine set intersection, worst case optimal joins, they all seem to be different aspects of the same underlying principle. So I'm very curious about the peculiarities in the sorting case.

See CPython's https://github.com/python/cpython/blob/main/Objects/listsort... for details about the sort. In fact, its "galloping" was inspired by a paper of which Demaine was a co-author (reference in the file already linked to). CPython's lists are implemented as contiguous C arrays of pointers (to Python objects). Any way of grafting a tree-ish structure on top of that would be unacceptably wasteful of space and/o…

Thank you for the explanation!
Post reply on HN