I dont understand how it is so special. Every single realworld sort I have seen are hybrid sorts. Very often merge sort + insertion sort or bubble sort for small sub-array.
Can you englight me ?
Timsort, the Python sorting algorithm
121–130 of 135 posts
Re: Timsort, the Python sorting algorithm
#122How to be THIS good as a Software Engineer?
Practice, challenge yourself constantly, seek mentorship, humbly request feedback and act on it, and devote your life to the craft, not your wallet or your family. I think. Read Hamming.
Re: Timsort, the Python sorting algorithm
#123You 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…
We did actually get to use it at work, to real performance benefit.
We have a leaderboard with a list of users, which is normally a list of users totalling between 2 to 50,0000, but in rare circumstances can be several million. The scores users can achieve are in a rather small range, perhaps only 450k valid different scores, and we were doing this sort on average once every 30 seconds.
What we ended up doing was switching to a radix sort when the list of users got to be very long, as it was substantially faster in those cases, making the user experience much better, as the leaderboard was much more up to date for the very large cases.
Re: Timsort, the Python sorting algorithm
#124Here is a video I made a while back to better visualize the runs of timsort:
https://www.youtube.com/watch?v=ZxLxf5xqqyE
Might be of interest...
Re: Timsort, the Python sorting algorithm
#125"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-...
[deleted]
Re: Timsort, the Python sorting algorithm
#126Earlier quoted context omitted.
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?
In this context, it means "much less." It's used that way sometimes in mathematical discussions.
Re: Timsort, the Python sorting algorithm
#127Earlier 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…
It sounds like it didn't break code, it just revealed that a lot of code was already broken. An invalid comparison function is a serious problem, and accepting unsorted output rather than fixing the damn bug is not a good workaround.
Obligatory xkcd: https://xkcd.com/1172 (Emacs Workflow)
Re: Timsort, the Python sorting algorithm
#128Isn't this the same idea as the Introsort[1], which was created in 1997 (four years earlier) and is the default sorting algorithm in C++'s standard library (and .NET framework since 4.5)?
Re: Timsort, the Python sorting algorithm
#129Earlier quoted context omitted.
And then 3 years later we have [0] and 6 years after that we have [1]. I appreciate Masters of the Universe types like Bloch and Lea contributing wickedly-efficient code, but somehow it's always mere mortals who end up mopping things up after the fact. Whether it's a bug in the actual algorithm or a "Comparison method violates its general contract!" exception that happens once in a blue moon, I think putting TimSort…
> I appreciate Masters of the Universe types like Bloch and Lea contributing wickedly-efficient code, but somehow it's always mere mortals who end up mopping things up after the fact I think this is the wrong way to look at the problem. Progress is always iterative. If a given person happens to make a bigger iteration, then people call them 'masters of the universe', but that iteration isn't inherently different from…
> I think this is the wrong way to look at the problem. Progress is always iterative. If a given person happens to make a bigger iteration, then people call them 'masters of the universe', but that iteration isn't inherently different from the normal, smaller kind of iteration.
+1. Bloch himself made the iteration over work by Arthur van Hoff and others at Sun before him.
Re: Timsort, the Python sorting algorithm
#130Earlier quoted context omitted.
Big O notation is about the theoretical upper bound of an algorithm. Clever data-based tricks like putting items in buckets or gathering statistics are unrelated to this notation as they rely on a certain consistency. Maybe you should call it average run time on typical data.
Radix sort is worst case O(n). (which is what I'm assuming the parent commenter is referring to) It's not n in common situations, but nlogn in pathological cases the way Timsort is. The reason is it "violates" the n logn lower bound of comparison sorts is because it isn't a comparison sort. Sort of like how hash table lookups "violate" the O(log n) average lower bound of binary tree lookups. It has different performa…
The n log n bound is for comparison sorts, which Radix Sort is not an instance of.