Dies ist die Methode, die Menschen oft beim Kartenspielen anwenden, um ihre Karten zu sortieren: Betrachte die Elemente eines nach dem anderen und füge jedes an seinen richtigen Platz zwischen den bereits betrachteten ein (wobei diese sortiert bleiben). Das gerade betrachtete Element wird eingefügt, indem die größeren Elemente einfach um eine Position nach rechts bewegt werden und das Element dann auf dem freigewordenen Platz eingefügt wird, wie Abbildung 2 zeigt.
Dieser Prozeß ist im folgenden Programm implementiert. Für jedes i von 2 bis N werden die Elemente a[1], ....., a[i] sortiert, indem a[i] an die entsprechende Stelle in der sortierten Liste von Elementen in a[1], ...., a[i - 1] gesetzt wird:
void straightinsertion (int a[ ], int N)
{
int i, j, v;
for ( i = 2; i >Marken |