Sortier-Algorithmen: binäres Einfügen

Idee: vergleiche mit mittlerem Element

füge x in a[l .. r] ein = {
  if (l = r) 
  then if x < a[l] 
       then x vor a[l] else x nach a[l]
  else m := mitte von l und r
       if x < a[m] 
       then füge x in a[l .. m - 1] ein
       else füge x in a[m + 1 .. r] ein
}

Vorsicht: werden alle Spezialfälle richtig behandelt? Diskussion im Seminar.-- Beachte: hier tun wir so, als ob das Beiseiteschieben der Elemente nichts kostet.