Abstract
The in-situ permutation algorithm due to MacLeod replaces by where is a permutation of using at most space. Kirshenhofer, Prodinger and Tichy have shown that the major cost incurred in the algorithm satisfies a recurrence similar to sequence of the number of key comparisons needed by the Quicksort algorithm to sort an array of randomly permuted items. Further, Hwang has proved that the normalized cost converges in distribution. Here, following Neininger and Rüschendorf, we prove the that rate of convergence to be of the order in the Zolotarev metric.
Connections
Explore this paper’s authors, topics and related work.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Reviews 0
Write a review
No reviews yet.
Discussion 0
Add a comment
No comments yet.