# Foreign language index sort order broken

When I create an MWE below, the sort order in the index is perfectly alphabetical. However when I work with a very large document which uses babel in the exact same manner, the order in the index is broken. I observe groups of alphabetically correctly ordered entries, but they are sprinkled with entries out of order. I cannot post the entire document as it is megabytes in size and have no idea how to troubleshoot, as it uses dozens of packages.

\documentclass{memoir}
\usepackage[utf8]{inputenc}
\usepackage[T1,T2A]{fontenc}
\usepackage[main=russian]{babel}
\usepackage{lipsum}
\usepackage{makeidx}
\makeindex
\begin{document}
\lipsum[1]

\index{жзи}

\clearpage
\lipsum[2]

\index{где}

\clearpage
\lipsum[3]

\index{абв}

\printindex
\end{document}


Edit (taken from the answer below):

I just reproduced the problem by adding more entries. The 2nd entry is in the wrong place:

\documentclass{memoir}
\usepackage[utf8]{inputenc}
\usepackage[T1,T2A]{fontenc}
\usepackage[main=russian]{babel}
\usepackage{lipsum}
\usepackage{makeidx}
\makeindex
\begin{document}
\lipsum[1]
\index{жзи}
\clearpage
\lipsum[2]
\index{где}
\clearpage
\lipsum[3]
\index{абв}
\clearpage
\lipsum[4]
\index{эюя}
\clearpage
\lipsum[5]
\index{шщы}
\clearpage
\lipsum[6]
\index{клм}
\printindex
\end{document}


There are a couple of problems to solve.

1. MakeIndex doesn't know about Russian and Cyrillic.

2. There are expansion issues with Cyrillic characters in pdflatex.

The first problem is solved using xindy. The second is solved by defining an ad hoc command for Cyrillic words to index.

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage[T1,T2A]{fontenc}
\usepackage[main=russian]{babel}
\usepackage{lipsum}
\usepackage{makeidx}
\makeindex

\newcommand{\rindex}[1]{\expandafter\index\expandafter{\detokenize{#1}}}

\begin{document}
\lipsum[1]
\rindex{жзи}
\clearpage
\lipsum[2]
\rindex{где}
\clearpage
\lipsum[3]
\rindex{абв}
\clearpage
\lipsum[4]
\rindex{эюя}
\clearpage
\lipsum[5]
\rindex{шщы}
\clearpage
\lipsum[6]
\rindex{клм}
\printindex
\end{document}


After running LaTeX, run

texindy -L russian -C utf8 <filename>.idx


and run LaTeX again (substitute <filename> with the actual file name).