Skip to main content
9 votes

Original reference for Huffman shaped Merge Sort?

I found the result hidden in an obscure 4p technical report: I share my results here in case others are interested. Knuth mentions runs in his description of "natural merge sort" (page 160 of the ...
J..y B..y's user avatar
  • 2,776
7 votes

Does Huffman coding always produce shorter codes than the Shannon code?

This is actually problem 5.12 in Cover and Thomas's information theory textbook; show that the probability distribution ${1/12,1/4,1/3,1/3}$ gives a counterexample. And if you want a really nice ...
Peter Shor 's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible