алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

Пример реализации сортировки вставками на Java:

public static void insertIntoSort(int[] arr) {
    int temp, j;
    for(int i = 0; i < arr.length - 1; i++){
        if (arr[i] > arr[i + 1]) {
           temp = arr[i + 1];
           arr[i + 1] = arr[i];      
           j = i;
           while (j > 0 && temp < arr[j - 1]) {
               arr[j] = arr[j - 1];               
               j--;
           }
           arr[j] = temp;             
        }        
    }
}