Метод вставки — один из прямых методов сортировки.

В исходном состоянии считаем, что сортируемая последовательность состоит из двух последовательностей: уже сортированной (на первом шаге состоит из единственного — первого элемента) и последовательности, которую еще необходимо сортировать. На каждом шаге из сортируемой последовательности извлекается элемент и вставляется в первую последовательность так, чтобы она оставалась сортированной. Поиск места вставки осуществляется с конца первой последовательности, сравнивая вставляемый элемент a_i с очередным элементом сортированной последовательности a_j. Если элемент a_i больше a_j, его вставляют вместо a_j+1, иначе сдвигают a_j вправо и уменьшают j на единицу. Поиск места вставки завершают, если элемент вставлен или достигнут левый конец массива. В последнем случае элемент a_i вставляют на первое место.

Существует прием, который позволяет отменить проверку достижения левой границы массива. Этот прием называется "проверка с барьером". С использованием этого приема проверка осуществляется так, чтобы из цикла поиска вставки в любом случае выход происходил по первому условию. Для этого достаточно поместить вставляемый элемент перед первым элементом массива, как элемент с индексом 0. Этот элемент и станет естественным барьером для ограничения выхода за левую границу массива.

/*n-число элементов сортируемого массива*/
for (i=2; i<n+1; i++) /*начиная со второго элемента до конца массива*/
  {
   b=a[i];
   a[0]=b;            /*барьер*/
   j=i-1;
   while(b<a[j])      /*пока очередной элемент сортированного массива */
      {               /*  больше i-го элемента*/
       a[j+1]=a[j];   /*сдвигаем элемент*/
       j=j-1;
       }
    a[j+1]=b;         /*как только найдено место, туда записываем b*/
   }

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

Для поиска места i-го элемента каждый раз потребуется выполнить от 1 до i-1 операции сравнения, т.е. в среднем i/2 операций сравнения. Значение i изменяется от 2 до n, т.е. выполняется n-1 проход, в каждом из которых происходит в среднем от 1 до n/2 сравнения. Суммарно в среднем для решения задачи требуется выполнить операции сравнения. Откуда вычислительная сложность метода в среднем равна О_ср(n²), хотя время выполнения примерно в два раза меньше, чем в методе выбора. В данном случае вычислительная сложность зависит от исходного расположения элементов массива.

В лучшем случае, когда массив уже упорядочен, поиск места вставки требует одного сравнения для каждого элемента, и количество сравнений равно n-1. Вычислительная сложность равна O(n).

В худшем случае, если элементы в исходном состоянии расположены в обратном порядке, поиск места вставки для каждого элемента потребует 1, 2, 3,..., n-1 сравнения, следовательно, всего потребуется n(n-1)/2 операций сравнения. Вычислительная сложность равна O(n²).

Таким образом, за счет ускорения сортировки в лучших случаях данный метод имеет лучшие временные характеристики, чем метод выбора.