Sortier-Algorithmen: lineares Einfügen

sortiere a[0 .. n-1] = {
  für i von 1 bis n-1 führe aus {
    füge a[i] in a[0 .. i-1] ein
  }
}
füge x in a[0 .. i-1] ein = {
  für k von i-1 bis 0 führe aus {
    if a[k] < x
       then a[k+1] = x; verlasse Schleife
       else a[k+1] = a[k]
  }
}

Laufzeit: Einfügen linear, Sortieren quadratisch.