sortiere (a) =
wenn Länge (a) <= 1,
dann gib a aus,
sonst
setze
b = (ungefähr) die Hälfte
der Elemente von a;
c = die restlichen Elemente von a;
b' = sortiere (b)
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, Teile und Herrsche (divide and conquer)