Если один 15 миллионый блок отсортирован, а затем 1 миллионный блок тоже отсортирован, наверно, можно применить пузырьковую сортировку, которая 1 раз пройдет и все расставит на свои места (хочется так думать, надо реализовать и посмотреть, что получится).

Сейчас подумал, и решил, что глупость сказал. Пузырьковую сортировку надо миллион раз прогнать, чтобы она все расставила на свои места, а это будет достаточно долго 1 млн * 15 млн.