insertion sort: sortowanie przez wstawianie

Algorytm sortowania polegający na wstawianiu kolejnych elementów listy w odpowiednie miejsce. Zbiór danych dzieli się na dwie części — posortowaną i nieposortowaną. Początkowo ta pierwsza zawiera tylko jeden element — pierwszy element zbioru. Następnie algorytm pobiera drugi i wstawia go odpowiednio przed lub za pierwszym. Ta sama operacja jest wykonywana dla pozostałych elementów z części nieposortowanej.