5 ms·
My immediate thought before reading the article is that shuffling is the inverse of sorting. To put another way, you can take a sorted list and apply a merge so
by conradludgate 3y ago
My immediate thought before reading the article is that shuffling is the inverse of sorting. To put another way, you can take a sorted list and apply a merge sort on it, but the comparison operation is random. Merge sort can work on data sets that are too large to fit in memory since you sort small sized blocks that do fit in memory, then merge using streaming
- CodesInChaos 3y agoYou can't just randomize the comparison operation, since that'd violate the requirements of a comparison function. MS made that mistake in their browser download dialog, which led to significant biases. You'd need to assign a random number to each item. But then you'd need to figure out a way to store this random number. Also, for in-memory data comparison-based sorting is much slower than shuffling. Both asymptotically (O(n log n) vs O(n)) and in practice. I did not investigate if sorting algorithms not based on comparisons (e.g. radix sort) have competitive performance. https://www.computerworld.com/article/2762287/microsoft-s-eu-ballot-fails-to-randomize-browser-order.html https://www.computerworld.com/article/2762287/microsoft-s-eu...
- anonymoushn 3y agoThe technique in TFA is very similar to radix sort.
- ndriscoll 3y agoIf you wanted to go down that line of thinking, you should be able to use a hash function to uniformly shuffle the keys within a larger space, and then apply your sort to that. No need to store the randomized keys. Probably performance wouldn't be as good as the OP article though.
- rcme 3y agoShuffling and sorting don’t seem related at all. Naively, I would expect shuffle to be linear in time complexity.
- anonymoushn 3y agoSorting too :)