Merge-Sort (Merge)

$$Id: merge.tex,v 1.3 2003/11/06 17:53:17 joe Exp $$

b' und c' sind Listen von Elementen (Zahlen)

füge b' und c' zusammen =
  solange ( b' nicht leer und c' nicht leer ) 
    wenn  erstes (b') < erstes (c')
      dann  ausgabe(erstes (b')); verkürze b';
      sonst ausgabe(erstes (c')); verkürze c';
  gib restliche Elemente von b' aus
  gib restliche Elemente von c' aus

in der Ausgabe stehen alle Element von b' und c' genau einmal.

Der Algorithmus erfüllt einen Vertrag:
wenn b' und c' zu Beginn aufsteigend geordnet sind, dann ist die Ausgabe aufsteigend geordnet.

Anzahl der Vergleiche ist $\le$ Länge von b $+$ Länge von c $-$ 1