Сортируете последний миллион любым алгоритмом.

Затем присоединяете его. Получается массив из двух отсортированных частей.

Затем подбираете какой-то алгоритм второй... Так и просится какое-то "просачивание", диффузия.