Normalverfahren:

16 3 22 11 9 7 4 3 Zuweisungen

3 16 22 11 9 7 4 4 Zuweisungen

3 11 16 22 9 7 4 5 Zuweisungen

3 9 11 16 22 7 4 6 Zuweisungen

3 7 9 11 16 22 4 7 Zuweisungen

3 4 7 9 11 16 22

gezählt jeweils 1 Zuweisung an Hilfsspeicher, 1 Zuweisung pro Stelle mit neuem Wert.

Problem: Wie wählt man Inkremente richtig?

Bei geeigneter Wahl kann man Laufzeit O(N log2 N) erreichen.