Gibt es dafür einen schnelleren Algorytmus?
Zuhauf. Such' Dir einen aus meinem Sortierkino aus. Ansonsten gibt es genug Seiten im Internet, die sich mit dem Laufzeitverhalten (der sog Komplexität) der Sortieralgorithmen beschäftigen. Den erstbesten auszusuchen ("ich dachte", "müsste") ist eine bequeme und vorerst schnelle, tendeziell jedoch langsame und schlechte Lösung. Es gibt sogar Sortieralgorithmen, die darauf spezialisiert sind, zu schon sortierten Mengen weitere - noch unsortierte - Mengen hinzuzufügen. Einer davon ist das Proportion Extend Sort (auch in meinem Programm zu finden).