Insertion sort je králem mezi jednoduchými třídícími algoritmy. Je stabilní, jednoduchý na implementaci, chová se inteligentně na již předtříděných polích a na malých polích (řádově desítky prvků) díky své jednoduchosti předběhne i QuickSort.
Insertion sort vidí pole rozdělené na 2 části - setříděnou a nesetříděnou. Postupně vybírá prvky z nesetříděné části a vkládá je mezi prvky v setříděné části tak, aby zůstala setříděná. Od toho jeho jméno - vkládá prvek přesně tam, kam patří a nedělá tedy žádné zbytečné kroky, jako například Bubble sort.
Na větších polích se samozřejmě začně projevovat handicap algoritmu, který spočívá v jeho časové složitosti O(n²) a začíná zaostávat za algoritmy chytřejšími.

Máme pole následujících prvků:

3

2

5

1

9

4

První prvek (3) budeme považovat za zatříděný a zbytek pole za nesedtříděný. Začneme tedy od druhého prvku (2), který si uložíme do pomocné paměti. Paměť: 2

3

2

5

1

9

4

Nyní budeme vytvářet místo pro tento prvek v již setříděné části, kam ho poté vložíme. Budeme posouvat prvky v setříděné části pole doprava tak dlouho, dokud buď nenarazíme na prvek menší (nebo stejný) nebo na začátek pole. Trochu matoucí může být, že jeden prvek bude v poli fyzicky zapsán 2x, protože jednou to bude znamenat mezeru (vyznačeno šedou barvou). Z teoretického hlediska je tam prázdno, jak můžete vidět dále na demonstraci algoritmu na videu. Zpátky k našemu případu - v paměti máme prvek 2, který je jistě menší než prvek 3, proto prvek 3 posuneme doprava. Tím se připravíme o prvek 2, ale ten máme v paměti,takže nám to nijak nevadí. Paměť: 2

3

3

5

1

9

4

Před vzniklou mezerou je již začátek pole, vložíme tedy na "prázdné" místo prvek z paměti. Setříděná část pole má již tedy 2 prvky. Paměť: 2

2

3

5

1

9

4

Půjdeme zatřídit další prvek, kterým je nyní prvek 5.

2

3

5

1

9

4

Zjistíme, že je před ním menší číslo, je tedy na správném místě. Velikost setříděné části se opět zvětší. Dalším na řadě bude prvek 1.

2

3

5

1

9

4

Paměť: 1

2

3

5

5

9

4

Paměť: 1

2

3

3

5

9

4

Paměť: 1

2

2

3

5

9

4

Paměť: 1

1

2

3

5

9

4

Zarazil nás až začátek pole, protože žádný jiný prvek nebyl menší než jednička. Prvek 9 očividně zůstane na místě.

1

2

3

5

9

4

Poslední je prvek 4, začneme tedy s posouváním.

1

2

3

5

9

4

Paměť: 4

1

2

3

5

9

9

Paměť: 4

1

2

3

5

5

9

Zastavíme se před prvkem 3 a vložíme prvek 4 z paměti na volné místo. Hotovo 😎

1

2

3

4

5

9

    public static void insertionSort(int[] list) {
        int item;
        int j;

        for (int i = 1; i <= (list.Length - 1); i++) 
        {
            // ulozeni prvku
            item = list[i];
            j = i - 1;
            while ((j >= 0) && (list[j] > item)) 
            {
                  list[j + 1] = list[j];
                  j--;
            }
            list[j + 1] = item;
        }

    }