Externes Sortieren

Problem: Sortieren auf Medien mit sequentiellem Lese- und Schreibzugriff.
Lösung: Wiederholtes Mischen von bereits sortierten Teilfolgen.

Ein Lauf ist eine monoton nicht fallende Teilfolge.

Lauf	Lauf	Lauf	Lauf

Gegeben 3 Magnetbänder, mit initial 0, n, 0 Läufen. Je 2 Bänder mischen ihre Läufe zusammen auf das dritte:

Band A:	0	0	8	3	0	2	1	0
Band B:	21	13	5	0	3	1	0	1
Band C:	0	8	0	5	2	0	1	0
								sortiert

(In jeder Spalte ist die momentane Anzahl der Läufe vermerkt.)

Allgemeine Regel:

     Sei fib(i) die i-te Fibonacci-Zahl.

    

Es habe Band	A	fib(i)	Läufe
	B	fib(i - 1)	Läufe
	C	0	Läufe

     dann mische fib(i - 1) Läufe von A und B zusammen auf Band C.