Метод вставки. Сортировка в паскале

Введение
Сортировка - процесс перегруппировки заданного множества объектов в некотором определенном порядке.
Сортировка предпринимается для того, чтобы облегчить последующий поиск элементов в отсортированном множестве.

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

Алгоритм работы сортировки вставками заключается в следующем:
в начале работы упорядоченная часть пуста;
добавляем в отсортированную область первый элемент массива из неупорядоченных данных;
переходим к следующему элементу в неотсортированных данных, и находим ему правильную позицию в отсортированной части массива, тем самим мы расширяем область упорядоченных данных;
повторяем предыдущий шаг для всех оставшихся элементов.

Пример сортировки
Рассмотрим алгоритм сортировки вставками на примере колоды игральных карт. Процесс их упорядочивания по возрастанию (в колоде карты расположены в случайном порядке) будет следующим. Обращаем внимание на вторую карту, если ее значение меньше первой, то меняем эти карты местами, в противном случае карты сохраняют свои позиции, и алгоритм переходит к шагу 2. На 2-ом шаге смотрим на третью карту, здесь возможны четыре случая отношения значений карт:
первая и вторая карта меньше третьей;
первая и вторая карта больше третьей;
первая карта уступает значением третьей, а вторая превосходит ее;
первая карта превосходит значением третью карту, а вторая уступает ей.

В первом случае не происходит никаких перестановок. Во втором – вторая карта смещается на место третьей, первая на место второй, а третья карта занимает позицию первой. В предпоследнем случае первая карта остается на своем месте, в то время как вторая и третья меняются местами. Ну и наконец, последний случай требует рокировки лишь первой и третьей карт. Все последующие шаги полностью аналогичны расписанным выше.

Рассмотрим на примере числовой последовательности процесс сортировки методом вставок. Клетка, выделенная темно-серым цветом – активный на данном шаге элемент, ему также соответствует i-ый номер. Светло-серые клетки это те элементы, значения которых сравниваются с i-ым элементом. Все, что закрашено белым – не затрагиваемая на шаге часть последовательности.