Názor k článku Unixová komprese v praxi: Bzip2 od KLON - Odvození není jednoduché, protože vyžaduje jistý matematický potenciál. Dovolím...

Odvození není jednoduché, protože vyžaduje jistý matematický potenciál.

Dovolím si ukázat zpětný chod bez třízení v O(N).

Projdu vzorek a spočtu výskyty jednotlivých znaků. O(N)
Projdu znovu a přiřadím každé pozici číslo podle vzoce #výskyt_znaku + Suma(#celkem_výskytů_znaku_mensich_nez_tento) O(N)
Tímto získám cyklickou permutaci, kterou projdu od naslédníka zapamatované pozice v setřízení. O(n)

Pameti to zabere pocty výskytů 256 * 4 + pole permutace N * 4.