Although the Block Sorting compression scheme has excellent
performance and speed, its optimality was not analyzed theoretically.
We propose two variants of the Block Sorting which are %shown to be
asymptotically optimal for any finite-order Markov source.
One of them encodes symbols as a block
and the other encodes symbols one by one by using arithmetic codes.