Sortieren durch 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
  }
}

Invarianten:

• (a₀,..., a_n-1) ist eine Permuation von (A₀,..., A_n-1)
• a₀$\le$a₁$\le$...$\le$a_i-1