Упорядоченный массив B' получается из В следующим образом: сначала он состоит из единственного элемента К1; далее для i=2,...,N выполняется вставка узла Кi в B' так, что B' остается упорядоченным списком длины i.
Например, для начального списка B=< 20,-5,10,8,7 > имеем:
/* сортировка методом вставки */ 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 (см. рис.26).
При сортировке вставкой требуется Q=(n-m)*(n-m) сравнений и не требуется дополнительной памяти.
Рис.26. Схема движения индексов при сортировке вставкой.
