Сортировка массивов русских символов и строк с участием буквы Ё

var a = new char[]
{
    'д',
    'е',
    'ё',
    'ж'
};
var b = a.OrderBy(x => x).ToList();
Console.WriteLine(string.Concat(b));

var a = new string[]
{
    "жар",
    "дом",
    "ели",
    "ёлка",
};
var b = a.OrderBy(x => x).ToList();
Console.WriteLine(string.Join(" ", b));

Здесь причиной вашего удивления является не странность алгоритмов BCL, а имплементация стандарта Unicode.

Документация стандарта Unicode Unicode® Technical Standard #10 / Unicode Collation Algorithm гласит (перевод мой):

1.1 Многоуровневое сравнение

Сортировка, требуемая человеческими языками, сложна. Чтобы правильно её имплементировать, используется многоуровневый алгоритм сравнения.

При сравнении двух слов, самым важным являются базовые буквы, например, отличие между И и Е. Акценты обычно игнорируются, если базовые буквы не совпадают. Различие в регистре (прописные/строчные) также обычно игнорируются, если базовые буквы или их акценты различны.

Что делать с пунктуацией, зависит от обстоятельств. В некоторых ситуациях, точка или запятая считается как бы отдельной базовой буквой. В других ситуациях пунктуация игнорируется, если и так есть отличия в базовых буквах, акцентах или регистре.

В случае равенства иногда проводится финальное сравнение: если других различий нет, сравниваются (нормализованные) code point'ы.

Таким образом, сравнение слов проводится следующим образом:

1. Отбрасываются различия регистра и акценты. Если сравнение установило, какое из слов больше, конец алгоритма.
2. Возвращаются назад акценты, проводится повторное сравнение. Если сравнение установило, какое из слов больше, конец алгоритма.
3. Возвращается назад регистр, проводится повторное сравнение. Если сравнение установило, какое из слов больше, конец алгоритма.

и. т. д.

Для русского языка по «принципу кроссворда» Ё считается акцентированным вариантом Е, а Й — акцентированным вариантом И.

Такой выбор стандарт для русского языка в Unicode, надеюсь, был согласован с лингвистами.

Как это поменять в .NET — как заставить считать Ё отдельной буквой, расположенной между Е и Ж, я сходу не скажу. (Но смотрите соседний ответ.)

Кстати, имплементация того или иного стандарта Unicode — фича не языка, а системы. BCL просит систему сравнить строки, чтобы не дублировать имплементацию Unicode. Это значит, что одна и та же программа, будучи проинсталлированной на Windows 7 и Windows 10, может вести себя по-разному по отношению к сортировке.

Уточнение

Для русской локали Й считается отдельной от И буквой, в то время как для английской Й считается акцентированным вариантом И. Буква Ё и там, и там считается акцентированным вариантом Е. Пример:

var strings = new[] { "Иа", "Йокогама", "Италия", "Ель", "Ёлочка" };
var en = CultureInfo.GetCultureInfo("en-US");
var ru = CultureInfo.GetCultureInfo("ru-RU");
var orderEn = strings.OrderBy(s => s, StringComparer.Create(en, false));
Console.WriteLine("en-US: " + string.Join(" ", orderEn));
var orderRu = strings.OrderBy(s => s, StringComparer.Create(ru, false));
Console.WriteLine("ru-RU: " + string.Join(" ", orderRu));

выдаёт такой результат:

en-US: Ёлочка Ель Иа Йокогама Италия
ru-RU: Ёлочка Ель Иа Италия Йокогама

Мораль этой истории: при сортировке строк всегда указывайте локаль!

В дополнение к ответу @VladD:

Как это поменять в .NET — как заставить считать Ё отдельной буквой, расположенной между Е и Ж, я навскидку не знаю.

Как вариант, можно реализовать свой IComparer, например так:

class MyStringComparer : IComparer<string>
{
    int IComparer<string>.Compare(string x, string y)
    {
        int result = CompareAlgorithm(x.ToLowerInvariant(), y.ToLowerInvariant());
        if (result != 0) return result;
        return CompareAlgorithm(x, y);
    }
    static readonly string symbols = " абвгдеёжзийклмнопрстуфхцчшщъыьэюяАБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.,:";
    int CompareAlgorithm(string x, string y)
    {
        int i = 0, j = 0;
        while(x.Length > i && y.Length > j)
        {
            int indexX = symbols.IndexOf(x[i]);
            int indexY = symbols.IndexOf(y[i]);
            if (indexX == -1)
            {
                ++i;
                continue;
            }
            if (indexY == -1)
            {
                ++j;
                continue;
            }
            if (indexX < indexY) return -1;
            if (indexX > indexY) return 1;
            ++i;
            ++j;
        }
        if (x.Length <= i && y.Length <= j) return 0;
        if (x.Length <= i) return -1;
        else return 1;
    }
}

Сравнение строк выполняется посимвольно, символы, участвующие при сравнении указываются в symbols, в желаемом порядке возрастания, символы, отсутствующие в symbols игнорируются.

В самом методе Compare сначала сравниваем без учета регистра и если выдается одинаковый результат, сравниваем с учетом регистра. Это поведение можно изменить. Если хотите всегда сравнивать с учетом регистра, оставьте метод в таком виде:

int IComparer<string>.Compare(string x, string y)
{
    return CompareAlgorithm(x, y);
}

Следующий код:

var a = new string[]
{
    "жар",
    "дом",
    "ель",
    "ёлка",
    "домовой",
    "д.ом",
    "д-ом",
    "ДОм"
};
var b = a.OrderBy(x => x, new MyStringComparer()).ToList();
Console.WriteLine(string.Join(" ", b));

Выдает такой результат:

д-ом дом ДОм домовой д.ом ель ёлка жар

Сортировка по умолчанию в Windows в целом и в .NET в частности всегда вызывает удивление.

Я задавал похожий вопрос на en.so.

Цитата из документации (чуть подправленная мной для читаемости):

Платформа .NET Framework использует три разных способа сортировки: по словам, по строкам и по порядковому номеру.

Соответственно, при сортировке нужно всегда указывать желаемый способ.