[daniel-cussen]

I know I need to compare it head to head against bytewise radix sort. I might do that and get back with the results. In the meantime, let me clarify. EDIT: Blas Mena and I did test it against radix sort, you can find it https://github.com/daniel-cussen/skylinesort/blob/master/src..., it tests with 4-bit radix sort and radix sort comes out 3% slower.

When I say that it can sort an array of size 2n faster than two arrays of size n it is because if you plot the asymptotic time, you find it's second derivative is negative (concave-up). This is because of the subtraction in the asymptotic time, O(k u - u log u + n). A Stanford professor was reluctant to accept an asymptotic time with a subtraction in it, but I explained it was really the logarithm of a division, ku-ulogu was actually u log(K/u) where K is 2^k, the total number of elements in the empty auxiliary array. log(K / u) is the same as log K - log u and log(K)=k, so you end up with k u - u log u, which has a negative second derivative when k is fixed.

When log u = k, skylinesort does indeed run in linear time, but it runs slower that linear time before that, and log u is never greater than k, by definition.