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
$\log_2(\frac{1}{\Pr_\mu(\pi)})+2n$ comparisons. A lower bound on the expected number of comparisons of $H(\mu)$ always holds, and a linear dependence on $n$ is also required.

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.
Moreover, the algorithm uses less comparisons
for more probable inputs: For every permutation $\pi$, the algorithm sorts $\pi$ by using at most $\log_2(\frac{1}{\Pr_\mu(\pi)})+2n$ comparisons. A lower bound on the expected number of comparisons of $H(\mu)$ always holds, and a linear dependence on $n$ is also required.

Improved the analysis: Now we show that the algorithm uses less comparisons for more probable permutations

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 
with expected number of comparisons that is at most H(\mu) + 2n, where H is the
entropy function. A lower bound of H(\mu) always holds, and a linear dependence
on n is also required.