>>11811142Basically you want to split the space into k intervals (not all the same width) and have a quick way for assigning points to these intervals using the cdf of the presupposed distribution.
You also want the number of points assigned to each interval to be roughly the same (n/k).
Then sort every list which takes c*k*(n/k)*log(n/k) time (c depends on your sorting algorithm).
Then concatenate each list to get your sorted list ( this only contributes + O(k).
Your intervals will need to get shorter where the pdf is large (in order to get roughly n/k per interval).
The precision required in the cdf will need to be higher for shorter intervals (where the pdf is large) so that not too many are misplaced.
You will need the error of the cdf to be roughly k/(n*p(x)) for a given point x.
You want k to be n/e^h in order to get your runtime down to c*n*h where h is o(log(n))
How do you prevent the overhead from the precision required in computing the cdf from growing with n?
The whole idea only works if you can prevent too many points from being placed in the same interval.
