Алгоритм сортировки вставкой заключается в следующем. Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.
Например, для начального списка B=< 20,-5,10,8,7 > имеем:
B=< 20,-5,10,8,7>  B'=< >
B=< -5,10,8,7 >    B'=< 20 >
B=< 10,8,7 >       B'=< -5,20 >
B=< 8,7  >         B'=< -5,10,20 >
B=< 7 >            B'=< -5,8,10,20 >
B=< >              B'=< -5,7,8,10,20 >
Функция insert реализует сортировку вставкой.
/*    сортировка  методом   вставки      */
float *insert(float *s, int m, int n)
 {
   int i,j,k;
   float aux;
   for (i=m+1; i<=n; i++)
     { aux=s[i];
       for (k=m; k<=i && s[k]=k; j--)  s[j+1]=s[j];
       s[k]=aux;
     }
   return(a);
 }
Здесь оба списка В и В' размещаются в массиве s, причем список В занимает часть s c индексами от i до n, а B' — часть s c индексами от m до i-1 (см. рис.1). При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.
Рис. 1.  Схема движения индексов при сортировке вставкой