A Note on Average-Case Sorting

摘要

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize the expected number of comparisons. We generalize Fredman's algorithm which is a variant of insertion sort and provide a basically tight upper bound: If mu is a distribution on permutations on n elements, then one may sort inputs from mu with expected number of comparisons that is at most H(mu) + 2n, where H is the entropy function. The algorithm uses less comparisons for more probable inputs: For every permutation pi, the algorithm sorts pi by using at most comparisons. A lower bound on the expected number of comparisons of H(mu) always holds, and a linear dependence on n is also required.