====================================================================
> 5. Сортировка простыми вставками.
====================================================================

                                 Алгоритм

             Все элементы условно разделяются на готовую
        последовательность a1 ... ai-1 и входную ai ... an. Hа
        каждом шаге, начиная с i=2 и увеличивая i на 1, берем i-й
        элемент входной последовательности и вставляем его на
        нужное место в готовую.

             Пример:

        Hачальные ключи         44 \ 55 12 42 94 18 06 67
                 i = 2          44 55 \ 12 42 94 18 06 67
                 i = 3          12 44 55 \ 42 94 18 06 67
                 i = 4          12 42 44 55 \ 94 18 06 67
                 i = 5          12 42 44 55 94 \ 18 06 67
                 i = 6          12 18 42 44 55 94 \ 06 67
                 i = 7          06 12 18 42 44 55 94 \ 67
                 i = 8          06 12 18 42 44 55 67 94 \

             При поиске подходящего места удобно 'просеивать' x,
        сравнивая его с очередным элементом ai и либо вставляя его,
        либо пересылая ai направо и продвигаясь налево.

             Просеивание может кончиться при двух условиях:

             1. Hайден ai с ключом, меньшим x.

             2. Достигнут конец готовой последовательности.

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

                                  Анализ

        Число сравнений
                             минимальное:           n - 1
                             среднее:         ( n^2 + n - 2 ) / 4
                             максимальное:   ( n^2 + n ) * / 2 - 1
        Количество пересылок
                             минимальное:       2 * ( n - 1 )

                             среднее:      ( n^2 + 9 * n - 10 ) / 4
                                                     
                             максимальное:  ( n^2 + 3 * n - 4 ) / 2
							 
    Примечания.
	
1. Если мы работаем с массивом, а не списком, то искать место вставки
очередного ai в готовую последовательность можно бинарным поиском,
ведь a1..a_i-1 уже отсортированы! 
При этом количество сравнений  снизится до O(nlogn),
но сортировка станет вести себя крайне неестественно (уже 
отсортированный массив обрабатывается дольше всего), а,
самое главное, количество пересылок по-прежнему останется O(n^2).
							 
2. При работе с массивами можно использовать и другое улучшение
InsertSort'a - ShellSort (описана в другом вопросе).

        Пример на Си - Tomas Niemann.
--------------------------------------------------------------------
typedef int item;          /* Тип сортируемых элементов */
typedef int tblIndex;      /* Тип ключей, по которым сортируем */

#define compGT(a,b) (a > b)   /* Функция сравнения  */

void insertSort(T *a, tblIndex lb, tblIndex ub) {
    item t;
    tblIndex i, j;

   /***********************
    * сортируем a[lb..ub] *
    ***********************/
    for (i = lb + 1; i <= ub; i++) {
        t = a[i];

        /* Сдвигаем элементы вниз, пока */
        /*  не найдем место вставки.    */
        for (j = i-1; j >= lb && compGT(a[j], t); j--)
            a[j+1] = a[j];

        /* вставка */
        a[j+1] = t;
    }
}