3 ms·
tldr: Assume input that are real numbers with some distribution. Approximate distribution with ML and use it to predict where every element should go. Using pre
by im3w1l 8y ago
tldr: Assume input that are real numbers with some distribution. Approximate distribution with ML and use it to predict where every element should go. Using prediction monotonous in value means no inversions but possible collisions. Fix that up into a sorted array.
The authors never proved that this will give O(n) in the presence of not-perfect estimation of the distribution, but their numerical experiments look promising.