Ein weiterer bekannter Sortieralgorithmus ist der **Insertion sort**. Dieser Algorithmus ist auch **stabil**, da im Falle von Duplikaten die Reihenfolge nach der sortierung beibehalten wird. Auch hier wird eine nicht leere Liste von Objekten zum sortieren erwartet.

Die Funktionsweise des Verfahrens ist ähnlich wie die des Selection sort. Zunächst wird ein Element gesucht, was eventuell sortiert werden muss. Danach wird die Liste mit einer weiteren Schleife durchlaufen, um so Werte zu finden, die größer sind als der zu sortierende Wert. Diese Elemente werden dann um eine Position nach rechts gerückt, falls man aufsteigend sortieren möchte.
Die äußere Schleife durchläuft alle Indizes einzelnt, während die innere Schleife für die Verschiebeoperationen zuständig ist.

* Insertion sort (c++)

```
#include <iostream>

void insertionSort(){
    const unsigned int SIZE = 10;
    unsigned int list[SIZE] = {56, 81, 3, 17, 35, 11, 8, 3, 17, 34};

    // for each element in the list
    for(unsigned int i = 0; i < SIZE; i++){
        unsigned int valueToSort = list[i];
        unsigned int k = i;

        // find a value to sort
        while( k > 0 && list[k-1] > valueToSort ){
            list[k] = list[k-1];
            k--;
        }
        list[k] = valueToSort;
    }

    for(unsigned int res = 0; res < SIZE; res++){
        std::cout << list[res] << "\n";
    }
}

int main(){
    insertionSort();
    return 0;
}
```

Quelle
https://www.researchgate.net/publication/266703295_Insertion_Sort_is_On_log_n [letzter Zugriff: 03.02.2020, 21:10]