Sei Länge vom alten Intervall =
2k - 1 | = | - + 1 | |||
2k | = | - + 2 | |||
2k - 1 | = | + 1 | |||
2k - 1 - 1 | = | = | |||
= | - ( + 1) + 1 | ||||
= | neue Intervalllänge im THEN-Zweig |
Beispiel für eine Folge von 31 sortierten Zahlen:
Schleifendurchlauf | 1 | 2 | 3 | 4 | 5 |
aktuelle Intervalllänge | 25 - 1 | 24 - 1 | 23 - 1 | 22 - 1 | 21 - 1 |
= 31 | = 15 | = 7 | = 3 | = 1 |
Anders formuliert:
n Zahlen verursachen höchstens n Schleifendurchläufe.