> -- Илья Ермаков писал(а):
> Затем подбираете какой-то алгоритм второй... Так и просится какое-то "просачивание", диффузия.Тоже подумал про диффузию, но нормального алгоритма что-то не выдумывается. Сдаётся мне, что проще будет отсортировать добавляемый массив, затем увеличить основной массив на необходимую величину и просто заполнить, начиная с хвоста, содержимым из обоих массивов. Это гарантированный и простой способ. Используется временный буфер из массива на 1 млн. записей (тот, что добавляем). Если нужно ужаться по памяти ещё сильнее, то поможет только карта индексов, а если дело только в скорости, то превосходство над полным QuickSort может быть существенным, а может и вовсе не быть, в зависимости от конкретных данных (к сожалению, конкретные формулы трудоёмкости выдавать я не обучен).