Merge-Sort (Sort)

sortiere (Folge a) = 
  wenn Länge (a) <= 1, 
    dann gib a aus, 
    sonst 
      Folge b = (ungefähr) die Hälfte 
            der Elemente von a;
      Folge c = die restlichen Elemente von a;
      Folge b' = sortiere (b)
      Folge c' = sortiere (c);
      füge b' und c' zusammen;

die Ausgabe von sortiere(a) enthält alle Element von a genau einmal und ist aufsteigend geordnet.

Entwurfsprinzip: Rekursion, divide and conquer