A note on self-improving sorting with hidden partitions

Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin

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

Knowledge Graph



Sign up or login to leave a comment