Здравствуйте, Андрюхаха!

Алгоритм сортировки вставкой подразумевает виртуальное разделение массива на две части - слева отсортированную и справа ещё неотсортированную. Каждый первый элемент правого подмассива вставляется в левый так, чтобы его отсортированность не нарушилась. То есть алгоритм вставки действует, например, так:
массив 4 7 1 10 3
подразумеваем, что самое начало отсортировано
4 | 7 1 10 3
вставляем 7 после 4
4 7 | 1 10 3
1 надо вставить перед 4
1 4 7 | 10 3
10 - после 7
1 4 7 10 | 3
3 - между 1 и 3
1 3 4 7 10|. Всё
Таким образом, задача сортировки сведена к поиску номера элемента массива, который меньше заданного числа, но следующий за ним элемент уже больше заданного числа. Применяется метод бинарного поиска. Этот метод применим только к отсортированному массиву.
Принцип следующий. Рассматривается сначала целый массив, допустим, [1 4 7 10] (вставка тройки). Он разбивается на две половинки, и граничный элемент сравнивается с заданным числом; если число превосходит границу, оно должно быть вставлено в правую половинку - так что рассматриваем её, иначе берём левую половинку. 3<4 => [1 4] 7 10. Далее повторяем алгоритм - половинизируем рассматриваемую часть и выбираем место, куда вставить требуемое число. 3>1 => 1 [4] 7 10 ; 3<4 => 1 [] 4 7 10. Вставляем - 1 [3] 4 7 10.
Реализация в приложении. Процедура sort принимает два параметра - сортируемый массив и его размер. Ничего не возвращает, просто модифицирует заданный массив.
Удачи!

Приложение:
#include <iostream>using namespace std;//Самое главное здесьvoid sort(int*& a, int s) { for (int i = 1; i < s; i++) { //i указывает первый элемент неотсортированной половины a int m = 0, n = i; //[m;n] - рассматриваемый отрезок массива, причём позиция 0 - перед начальным элементом массива, 1 - между первым и вторым, и т.д. while (n != m) { //Цель - сузить рассматриваемый отрезок до такого, чтоб не осталось сомнений, куда помещать a[i]. Работает и условие a[n]!=a[m], причём даже несколько быстрее int t = (m + n) / 2; //Середина отрезка if (a[i] >= a[t]) m = t + 1; //Если a[i] превышает средний элемент, новый отрезок будет справа от него, т.е. новая левая граница сразу за ним else n = t; //Иначе правую границу поместим сразу перед a[t] }//Нашли отрезок [m;m] длины 0, где должен оказаться a[i] int q = a[i];//Запомним вставляемый элемент for (int k = i - 1; k >= m; k--) a[k + 1] = a[k];//Сдвинем массив, образовав нишу для q и затерев a[i] a[m] = q;//Вставляем//перемещаем виртуальную грань между отсортированой и неотсортированной половинами (см. i++), и повторяемся }}int main() { int a[20] = {13, 7, 15, 17, 2, 9, 12, 11, 3, 3, 8, 1, 14, 4, 10, 5, 16, 6, 3, 3};//Пример sort(a, 20); for (int i = 0; i < 20; i++) cout<<a[i]<<" "; cout<<"\n"; system("pause"); return 0;}