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.

$\underbrace{3~~~~~~ 7~~~~~~ 8}$	$\underbrace{2~~~~~~ 9}$	$\underbrace{4}$	$\underbrace{1~~~~~~ 5~~~~~~ 6}$
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.