Natürliches 2-Wege-Mergesort

Verschmelzprozeß wird nicht mit einelementigen Listen begonnen, sondern mit möglichst langen bereits sortierten Teilfolgen.

Jeweils zwei benachbarte Teilfolgen werden verschmolzen.

Beispiel:

3 6 | 5 7 9 | 1 8 | 0 2 4

3 5 6 7 9 | 0 1 2 4 8

0 1 2 3 4 5 6 7 8 9

Algorithmus nutzt Vorsortierung aus: falls Liste bereits sortiert, so wird das in O(N) Schritten festgestellt.