Although the Block Sorting compression scheme~\cite{BurWhe94} has excellent performance and speed, its optimality was not analyzed theoretically. The context sorting~\cite{Yokoo96} may be regarded as an on-line version of the Block Sorting. Because it is asymptotically optimal for any finite-order Markov source, the Block Sorting is also asymptotically optimal if we encode consecutive \$l\$ symbols at a time and if \$l\$ tends to infinity. The Block Sorting uses the Burrows-Wheeler transformation (BWT) which permutes an input string. The permutation is defined by lexicographic order of contexts of symbols. If we assume that %the string is generated by a \$k\$-th order Markov source, that is, symbol probability is defined by preceding \$k\$ symbols called context, symbols whose contexts are the same are collected in consecutive regions after the BWT. % Sadakane~\cite{Sada97c} proposed a variant of the Block Sorting and it is asymptotically optimal for any finite-order Markov source if permutation of symbols whose contexts are the same is random. However, the variant encodes \$l\$ symbols as a block and therefore it is not practical %because of compression speed and required memory. because \$l\$ is large. %Consequently it is necessary to develop practical compression schemes. %and analyze their compression ratio. We propose two compression schemes not using blocks but encoding symbols one by one by using arithmetic codes. The move-to-front transformation is not used. The former encodes symbols by different codes defined by symbol frequencies in contexts. It is asymptotically optimal for \$k\$-th order Markov sources. However, it is available only if the order \$k\$ of the source is already known. % The latter divides the permuted string into many parts and encodes symbols using different arithmetic codes by the parts. Each part has symbols whose contexts are the same. If the permutation is random, the scheme is asymptotically optimal for any finite-order Markov source. %As a result, we obtain a guide to design compression schemes which are %easily implemented and theoretically have good performances. The permutation in the BWT is not completely random. For example, if three or more contexts are the same and they overlap each other, symbols following them appear in the permuted string in original order or its reversal. However, we conjecture that the permuted string is memoryless and our schemes work.