Здравствуйте, Буравчик, Вы писали:

_FR>>Спасибо. RemoveAt всегда удаляет последний элемент из списка, поэтому она сложности добавлять не должна.
_FR>>Далее бинарным поиском находится, куда вставить новый элемент и это как раз и есть логарифм. Нет?

Б>Так еще insert есть, в середину

То есть вот это вот по сути имеет линейную сложность:

var index = list.BinarySearch(item);
list.Insert(index >= 0 ? index : ~index, item);

_FR>>Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?
Б>Чтобы определить логарифм там или нет, надо мерять не весь этап мержа, а только on-CPU, т.е. только работу с items, без диска
Б>P.S. Большая разница во времени могла также получиться из-за типа диска HDD/SSD/NVME

Мне выдали такие вот:

Как ориентир по времени — 10Гб файл генерируется около 2,5 минут, сортируется — 9 (кстати, это не самое быстрое решение).
Дополнительный ориентир — при сортировке 1Гб используется 2-2,5 Гб памяти.

На моём стареньком лаптопе, хорошем, но совсем не геймерском с ССД ессно генерация файла в 10Г занимает 35 секунд, сортировка 140с (памяти при этом расходуется меньше гига).
Если мне сказали, что моя программа работает 130 секунд на гигабайтном файле и это медленно, значит у них есть программы, которые там же работают значительно быстрее.

Я подозреваю, что дело тут может быть или в работе с диском или в каком-то принципиально другом подходе, потому что иначе не вижу, почему вдруг мой код работает в 10 раз медленнее, чем их.
Вот и интересно, в чём же именно я так промахнулся.