A note on self-improving sorting with hidden partitions
classification
💻 cs.CG
keywords
hiddenoutputpartitionsself-improvingsortingalgorithmcontainsdenotes
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.