A note on self-improving sorting with hidden partitions

02/01/2019
by   Siu-Wing Cheng, et al.
0

We study self-improving sorting with hidden partitions. Our result is an optimal algorithm which runs in expected time O(H(π(I)) + n), where I is the given input which contains n elements to be sorted, π(I) is the output which are the ranks of all element in I, and H(π(I)) denotes the entropy of the output.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset