Бинарное дерево или сортировка? C++

Динамическое бинарное дерево займёт в памяти огромное количество памяти для ссылок (три штуки) и баланс. Миллиардные попытки выделить память для каждого узла займёт времени на всю область вашего терпения. Можно конечно первым проходом посчитать количество данных в файле и выделить одноразово память для массива узлов деревьев. Но намного проще выделить память в три раза меньше для обычного массива данных и произвести быструю сортировку. Результат: подсчёт количества данных, запись в обычный массив, quick-sort.

Быстрее будет сортировка в массиве. Меньше промахов в кэше, меньше расход памяти, да и быстрая сортировка STL работает очень хорошо. Миллионы чисел сортируются за секунды.

Если у вас есть возможность узнать, сколько элементов хранится в памяти, то могу посоветовать заранее выделить необходимо количество памяти в массиве. В случае использования std::vector, это будет функция reserve или сразу передать в конструктор необходимое количество элементов.

Что касается считывания, то стоит помнить, что данные все равно подгружаются из буфера (т.е. из файла загружается какая-то часть в буфер, например, 4КБ, а потом читается с буфера, когда вы используете считывание), поэтому происходит считывание достаточно быстро.

И ещё одна вещь, которая может сэкономить вам память и увеличить скорость. Это если в файле они хранятся в бинарном виде, а не в текстовом. Это также позволит узнать, сколько чисел хранится в файле и потом выделить память.