Есть такая задачка:
Дано 15 миллионов неотсортированных записей, требуется их отсортировать и обработать.
Затем, в конец 15 миллионного массива добавляется еще 1 миллион записей, требуется, чтобы весь 16 миллионный массив был отсортирован (первые 15 уже отсортированы, а последний миллион нет) и нужно его обработать.
Затем к 16 миллионному массиву добавляется еще 1 миллион, требуется, чтобы весь 17 миллионный массив был отсортирован и так далее, до тех пор пока массив не станет 30 миллионным.

Пока я сортирую с помощью алгоритма, QuickSort, сортировка занимает порядка 1 минуты, есть еще преимущество, что не требуется дополнительный массив (все записи занимают порядка 500 Мегабайт памяти). Но недостаток в том, что QuickSort пересортировывает весь массив и не учитывает, что, например, первые 15 миллионов записей уже отсортированы.

Может кто-нибудь посоветует более эффективную сортировку? Желательно еще, чтобы не требовался дополнительный массив, но это условие не обязательное.