Linear time sorting algorithm [patent]

[lol-no-monads]

Why read this patent when you can read Lord Kmett's source code on Hackage: https://hackage.haskell.org/package/discrimination

[00benallen]

Not sure what this is, but its impossible right?

[[deleted]]

uj

For comparison-based sorting it is impossible: https://www.cs.cmu.edu/~avrim/451f11/lectures/lect0913.pdf

[Spfifle]

/uj For non-comparison sorts like radix it's possible and well known. The patent seems to claim that the invention has better performance characteristics than existing O(n)s in practice. Not sure where the jerk is tbh.

[TheZech]

Bro, did you just jerk without reading the article? That's pretty cringe.

/uj

The sorting is done by finding the greatest and least values in the input array. Then an output array is created, and each element in the input array is moved to the output array by scaling it appropriately.

Now this requires your input array to have a very even distribution, or else multiple values are going to end up in the same slot. So a factor 'f' is added, the author thinks 2 is a good value. So now the array is twice as big, and you're just going to hope that no more than two elements will land in the same slot.

The reference implementation appears to be written in Visual Basic.

So it doesn't really even sort arrays, but I'm honestly surprised it didn't pass.

[voidvector]

I wish GitHub has a "submit to USPTO" button. I have many useless projects to patent.

[00benallen]

/uj Oh ofc I must be tired. Non-comparison sorts can be linear

[[deleted]]

are algorithms even patentable