Исходный массив данных (несколько десятков тысяч элементов) уже упорядочен по возрастанию. Нужно добавлять к этому массиву новый элемент, чтобы массив после каждого добавления оказывался опять упорядоченным.
Алгоритмов много, просто не знаю какой выбрать наилучший. Дополнительной памяти можно найти, главное скорость.