Сортировка Вставкой

Сортировка вставкой - это метод который почти настолько же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отсортированными).

type Index = 0..n; var a: array[1..n] of elem; procedure Insert;     var i,j: index;     x: elem;     begin     for i:= 1 to n do     begin         x:= a[i]; a[0]:= x; j:= i-1;         while x.key < a[j].key do         begin         a[j+1]:= a[j]; j:= j-1;         end;         a[j+1]:= x;     end;     end;

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