Second, I have independently invented this (quicksort on string prefixes) at my time at CWI, although I didn't end up publishing it, because...
Third, this was already published in the original 1961 Quicksort paper by Hoare: https://www.cs.ox.ac.uk/files/6226/H2006%20-%20Historic%20Qu.... Near the end, the section on "Multi-word keys" describes a quicksort that partitions on just the first word, and only accesses the next word for the equality partition.
So as is usual for software patents, this patent never should have been awarded.
It's kind of insane that such an obvious optimization can be patented, I have to imagine that it has been invented independently dozens if not hundreds of times.
Second, I have independently invented this (quicksort on string prefixes) at my time at CWI, although I didn't end up publishing it, because...
Third, this was already published in the original 1961 Quicksort paper by Hoare: https://www.cs.ox.ac.uk/files/6226/H2006%20-%20Historic%20Qu.... Near the end, the section on "Multi-word keys" describes a quicksort that partitions on just the first word, and only accesses the next word for the equality partition.
So as is usual for software patents, this patent never should have been awarded.
I think this is inventors blog https://smalldatum.blogspot.com/2026/01/common-prefix-skippi...
Thanks for sharing.
What does naturally even mean here. How is a 64 byte register's (zmm0) size any less natural?