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 minimizethe expected number of comparisons. We generalize Fredman's algorithm whichis a variant of insertion sort and provide a basically tight upper bound: If \mu isa 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 theentropy function. A lower bound of H(\mu) always holds, and a linear dependenceon n is also required.