Merge-Sort (Merge)

Id: merge.tex,v 1.2 2006-10-30 16:03:17 waldmann 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.

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