Но мне таки кажется, что правильный способ взять RDBMS, создать базу с двумя таблицами.
Первая таблица с одной колонкой для строк, она же primary key.
Вторая колонка с foreign key на первую таблицу, int32 или int64 колонкой для чисел, и например secondary key из колонки для чисел.
Последовательно прочитать один раз файл.
Для каждой строки найти или добавить её в первую таблицу, потом добавить строку во вторую таблицу.
Потом один раз прочитать всю базу, и в цикле написать выходной файл.
Для RDBMS лучше всего взять SQLite, потому что оно in-process, и в идеале понастраивать его для максимальной производительности и минимальной durability.
Или если не хочется тащить dependencies, а на компьютере Windows, можно ESENT ещё.
Остальные способы изрядно хуже.
Стандартные коллекции вроде List или Dictionary поддерживают максимум 2 миллиарда значений (потому что число элементов int32), 100GB файл скорее всего будет больше.
Кроме того, даже если хранить по 8 байт на строчку, для объёмов в той задаче вероятно падение с out of memory.
Если что-то самому колхозить на тему временных файлов на диске, скорее всего получится или сильно медленнее, или адски сложное.
Таблицы в базах данных состоят из B-trees, хорошо подходят для задачи, но самому их запилить изрядно сложно.
