Многое зависит от задачи, от того, что за данные добавляются в конец, и от того, что "дешевле" - сравнение или обмен элементов местами.

Например, если добавляемый массив часто имеет данные, которые будут помещены в конец результирующего массива, а не распределены по нему равномерно, то для начала можно второй массив не сортировать, а просто узнать минимальное значение его элемента. После этого можно сильно ограничить область применения QuickSort'а на завершающем шаге, и это уже будет существенная оптимизация.

Если обмен дорогой, а сравнения дешёвые, то можно составить карту индексов с тем, чтобы через максимум 1 млн. обменов получить отсортированный массив. Под картой индексов подразумевается массив с 16 млн. целочисленных значений, каждое i-e его значение - это индекс элемента исходного массива, который должен оказаться на i-м месте в результирующем массиве. Для получения карты индексов, очевидно, добавляемый массив надо предварительно отсортировать тем же QuickSort'ом.