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

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

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

_FR>Экспериметы вроде это подтверждают: при разбиении гигабайтного файла на куски по 10,000 строк (198 файлов получается) время собственно мёрджа 00:00:07.6173967, при разбиении этого же файла на куски по 1000 строк (1,976 файлов) время мёрджа 00:00:13.2285478. Точно у меня там не логарифм?

Чтобы определить логарифм там или нет, надо мерять не весь этап мержа, а только on-CPU, т.е. только работу с items, без диска

P.S. Большая разница во времени могла также получиться из-за типа диска HDD/SSD/NVME