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.