The case for a learned sorting algorithm

Re:The case for a learned sorting algorithm by qsort on Monday October 19, 2020 @04:08PM (#24830396)

If you know the distribution of your data (in the sense that you are guaranteed that each datapoint is iid with a distribution described by some known PDF f : R -> R), you can sort in O(N) with probability 1.

[ Parent | on HN ]

Re:The case for a learned sorting algorithm by 0-_-0 on Monday October 19, 2020 @04:42PM (#24830778)

That's almost never the case in practice. What distribution the data is drawn from on the other hand can often be known or approximated.

[ Parent | on HN ]

Re:The case for a learned sorting algorithm by qsort on Monday October 19, 2020 @04:48PM (#24830841)

What do you mean "is drawn from"? Isn't the previous condition a reasonable characterization of "you know what distribution it's drawn from"?

[ Parent | on HN ]

Re:The case for a learned sorting algorithm by 0-_-0 on Monday October 19, 2020 @05:00PM (#24830969)

Let's say you draw 1 million samples from a uniform distribution between 0 and 1. I'm saying that if you know the distribution you can sort in O(N log(log(N))). Are you claiming you can sort them in O(N)?

[ Parent | on HN ]

Re:The case for a learned sorting algorithm by qsort on Monday October 19, 2020 @05:15PM (#24831101)

Assuming "1 million" is a proxy for taking the limit to infinity, i.e. the usual asymptotic setting, if you are willing to accept that the algorithm will "only" work with probability 1, then yes, I can.

Let N be the size of the array. Create N new empty lists, numbered from 0 to N-1. Divide [0, 1) in N equal brackets B0 = [0, 1/n); B1 = [1/n, 2/n]... BN-1 = [(n-1)/n, 1). For each element, determine the bracket it falls in and append it to the corresponding list. Sort each list. Because of the uniformity hypothesis, for n -> infinity, the probability that each bracket contains O(1) elements goes to 1, therefore the running time is O(N) with probability 1.

[ Parent | on HN ]

Re:The case for a learned sorting algorithm by nemoniac on Monday October 19, 2020 @05:52PM (#24831453)

I'd really like to read up on this. Do you have a source?

[ Parent | on HN ]

Re:The case for a learned sorting algorithm by qsort on Monday October 19, 2020 @07:22PM (#24832179)

It's really dead simple, look at my other comment in the same thread. The only caveat is that all those fancy words before are actually necessary minimal hypotheses, not just fancy words.

[ Parent | on HN ]