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

                                  Анализ

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

Пример на Си - 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;
    }
}

Выберем случайным образом какой-то элемент х и просмотрим массив, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший х. Поменяем их местами и продолжим процесс просмотра с обменом, пока просмотры не встретятся где-то в середине массива. В результате массив разделится на две части: левую - с ключами, меньшими х и правую - с ключами, большими х. Этот шаг называется разделением. Х - центром. К получившимся частям рекурсивно применяем ту же процедуру. В результате получается очень эффективная сортировка.

              Пример рекурсивной QuickSort

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

#define CompGT(a,b) (a > b)

tblIndex partition(T *a, tblIndex lb, tblIndex ub) {
     item t, pivot;
    tblIndex i, j, p;

   /**********************************
    *  разделение массива a[lb..ub]  *
    **********************************/

    /* Выбираем центр - pivot */
    p = lb + ((ub - lb)>>1);
    pivot = a[p];
    a[p] = a[lb];

    /* сортируем lb+1..ub относительно центра */
    i = lb+1;
    j = ub;
    while (1) {
        while (i < j && compGT(pivot, a[i])) i++;
        while (j >= i && compGT(a[j], pivot)) j--;
        if (i >= j) break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
        j--; i++;
    }

    /* центр в a[j] */
    a[lb] = a[j];
    a[j] = pivot;

    return j;
}

void quickSort(T *a, tblIndex lb, tblIndex ub) {
    tblIndex m;

   /**************************
    *  сортируем  a[lb..ub]  *
    **************************/

    while (lb < ub) {

        /* сортировка вставками для малых массивов */
        if (ub - lb <= 12) {
            insertSort(a, lb, ub);
            return;
        }

        /* разделение пополам */
        m = partition (a, lb, ub);

        /* Уменьшаем требования к памяти:    */
        /*  меньший сегмент сортируем первым */
        if (m - lb <= ub - m) {
            quickSort(a, lb, m - 1);
            lb = m + 1;
        } else {
            quickSort(a, m + 1, ub);
            ub = m - 1;
        }
    }
}

Hа практике для увеличения быстроты, но не асимптотики, можно произвести несколько улучшений:

Пример, входящий в стандартную реализацию Си использует многие из этих улучшений.

Стандартная реализация итерационной QuickSort
------------------------------------------------

#include 
#define MAXSTACK (sizeof(size_t) * CHAR_BIT)

static void exchange(void *a, void *b, size_t size) {
    size_t i;

    /******************
     *  обменять a,b  *
     ******************/

    for (i = sizeof(int); i <= size; i += sizeof(int)) {
        int t = *((int *)a);
        *(((int *)a)++) = *((int *)b);
        *(((int *)b)++) = t;
    }
    for (i = i - sizeof(int) + 1; i <= size; i++) {
        char t = *((char *)a);
        *(((char *)a)++) = *((char *)b);
        *(((char *)b)++) = t;
    }
}

void qsort(void *base, size_t nmemb, size_t size,
        int (*compar)(const void *, const void *)) {
    void *lbStack[MAXSTACK], *ubStack[MAXSTACK];
    int sp;
    unsigned int offset;

    lbStack[0] = (char *)base;
    ubStack[0] = (char *)base + (nmemb-1)*size;
    for (sp = 0; sp >= 0; sp--) {
        char *lb, *ub, *m;
        char *P, *i, *j;

        lb = lbStack[sp];
        ub = ubStack[sp];

        while (lb < ub) {

            /* выбираем центр и меняемся с 1м элементом */
            offset = (ub - lb) >> 1;
            P = lb + offset - offset % size;
            exchange (lb, P, size);

            /* разделение в два сегмента */
            i = lb + size;
            j = ub;
            while (1) {
                while (i < j && compar(lb, i) > 0) i += size;
                while (j >= i && compar(j, lb) > 0) j -= size;
                if (i >= j) break;
                exchange (i, j, size);
                j -= size;
                i += size;
            }

            /* центр в A[j] */
            exchange (lb, j, size);
            m = j;

            /* Меньший сегмент продолжаем обрабатывать, больший - в стек */
            if (m - lb <= ub - m) {
                if (m + size < ub) {
                    lbStack[sp] = m + size;
                    ubStack[sp++] = ub;
                }
                ub = m - size;
            } else {
                if (m - size > lb) {
                    lbStack[sp] = lb;
                    ubStack[sp++] = m - size;
                }
                lb = m + size;
            }
        }
    }
}

Hазовем пирамидой последовательность элементов hl , hl+1 , ... , hr такую, что

          Геометрическая интерпретация пиромиды:

                      h1
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
               h2            h3
              / \            / \
             /   \          /   \
           h4    h5       h6     h7
          /  \  /  \     / \   /  \
         h8  h9 h10 h11  h12 h13 h14 h15

      Для последовательности 06 42 12 55 94 18 44

                      06
                     /  \
                    /    \
                   /      \
                  /        \
                 /          \
               42            12
              / \            / \
             /   \          /   \
           55    94        18   44

Добавление элемента в готовую пирамиду:

Фаза 1: построение пирамиды

Пусть дан массив h1 ... hn . Ясно, что элементы hn/2 + 1 ... hn уже образуют 'нижний ряд' пирамиды, так как не существует индексов i , j : j = 2*i ( или j = 2*i + 1 ). То есть тут упорядочивания не требуется.

Hа каждом шаге добавляется новый элемент слева и 'просеивается' на место. Вот иллюстрация процесса для пирамиды из 8-и элементов:

      44  55  12  42 [94] 18  06  67
      44  55  12 [42] 94  18  06  67
      44  55 [06] 42  94  18  12  67
      44 [42] 06  55  94  18  12  67
     [06] 42  12  55  94  18  44  67

Фаза 2: сортировка

Для того, чтобы рассортировать элементы, необходимо выполнить n шагов просеивания: после каждого шага очередной элемент берется с вершины пирамиды. Hа каждом шаге берем последний элемент Х, верхний элемент пирамиды помещается на его место, а Х просеивается на свое 'законное'. В этом случае необходимо совершить n - 1 шагов. Пример:

      06  42  12  55  94  18  44  67  
      12  42  18  55  94  67  44 [06]
      18  42  44  55  94  67 [12] 06
      42  55  44  67  94 [18] 12  06
      44  55  94  67 [42] 18  12  06
      55  67  94 [44] 42  18  12  06
      67  94 [55] 44  42  18  12  06
      94 [67] 55  44  42  18  12  06

Hу вот мы м получили отсортированную последовательность, только в обратном порядке. Изменяя сравнения на противоположные, получаем функцию Heapsort на Паскале.

Прекрасной характеристикой этого метода является то, что среднее число пересылок - (n*log n)/2 и отклонения от этого значения сравнительно малы.

{ сортируем массив типа 'item' по ключу 'a.key' }

procedure Heapsort;
 var i,l: index; x: item;

procedure sift;
 label 13;
 var i, j: index;
begin i := l; j := 2*i; x := a[i];
 while j <= r do
 begin if j < r then
  if a[j].key < a[j+1].key then j := j+1;
  if x.key >= a[j].key then goto 13;
  a[i] := a[j]; i := j; j := 2*i
 end;
 13: a[i] := x
 end;

 begin l := (n div 2) + 1; r := n;
  while l > 1 do
   begin l := l - 1; sift
   end;

  while r > 1 do
   begin x := a[l]; a[l] := a[r]; a[r] := x;
     r := r - 1; sift
 end
end { heapsort }

К сожалению, или к счастью, единица информации в современной технике способна применять лишь 2 значения: 1 и 0. А значит, любые компьютерные данные тоже могут принимать ограниченное количество значений, так как состоят из некоторого числа битов ;-)).

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

Разрядность данных ( количество возможных значений элементов k) - m. Если мы сортируем слова, то элемент сортировки - буква. m = 33. Если в самом длинном слове 10 букв, k = 10. Обычно мы будем сортировать данные по ключам из k байт, m=255.

Пусть у нас есть массив source из n элементов по одному байту в каждом. Для примера можете выписать на листочек массив source = { 7,9,8,5,4,7,7 }, и проделать с ним все операции, имея в виду m=9.

for ( i = 0 ; i < 255; i++ ) distr[i]=0;
for ( i = 0 ; i < n ; i++ ) distr[source[i]] = distr[[i]] + 1;

Для нашего примера будем иметь distr = { 0, 0, 0, 0, 1, 1, 0, 3, 1, 1 }, то есть i-ый элемент distr[] - количество ключей со значением i.

int index[256];
index [0]=0;
for ( i = 1 ; i < 255; i++ ) index[i]=index[i-1]+distr[i-1];

В index[i] мы поместили информацию о будущем количестве символов в отсортированном массиве до символа с ключом i. Hапример, index[8] = 5 : имеем 4, 5, 7, 7, 7, 8. А теперь заполняем новосозданный массив sorted размера n:

for ( i = 0; i < n ; i++ )
     {
      sorted[ index[ source[i] ] ]=source[i];
// попутно изменяем index уже вставленных символов, чтобы
// одинаковые ключи шли один за другим:
      index[ source[i] ] = index[ source[i] ] +1;
     }

Итак, мы научились за O ( n ) сортировать байты. А от байтов до строк и чисел - 1 шаг. Пусть у нас в каждом числе - k байт. Будем действовать в десятичной системе и сортировать обычные числа ( m = 10 ).

      сначала они в        сортируем по младшему     на один
       беспорядке:               разряду:             выше:     и еще раз:
           523                      523                523         088
           153                      153                235         153
           088                      554                153         235
           554                      235                554         523
           235                      088                088         554

Hу вот мы и отсортировали за O ( k*n ) шагов. Если количество возможных различных ключей ненамного превышает общее их число, то поразрядная 'сортировка' оказывается гораздо быстрее даже 'быстрой сортировки' !

Реализация на C++ для long int'ов.

 #include 
 #include < stdlib.h>
 #include < string.h>

 void radix (int byte, long N, long *source, long *dest)
 {
  long count[256];
  long index[256];
  memset (count, 0, sizeof (count));
  for ( int i=0; i>(byte*8))&0xff]++;
  index[0]=0;
  for ( i=1; i<256; i++ ) index[i]=index[i-1]+count[i-1];
  for(i=0;i>(byte*8))&0xff]++]=source[i];
 }

 void radixsort (long *source, long *temp, long N)
 {
  radix (0, N, source, temp);
  radix (1, N, temp, source);
  radix (2, N, source, temp);
  radix (3, N, temp, source);
 }

 void make_random (long *data, long N)
 {
  for ( int i=0; i < N; i++ ) data[i]=rand()|(rand()<<16);
 }

 long data[10000];
 long temp[10000];

 void main (void)
 {
  make_random(data, 10000);
  radixsort (data, temp, 10000);
  for ( int i=0; i<100; i++ ) cout << data[i] << '\n';
 }

Многофазная сортировка

Этот тип сортировки относится к так называемым 'сортировкам слиянием'. Слиянием называется процесс объединения нескольких упорядоченных серий в одну.

Пример для 3-х серий, слияемых на 4-ю:

    3 7 9      3 7 9        3 7 9          7 9             7 9
  { 2 4 6  1 { 2 4 6  1 2 { 4 6    1 2 3 { 4 6   1 2 3 4 { 6
    1 5 8      5 8          5 8            5 8             5 8

               7 9                7 9                 9
   1 2 3 4 5 { 6    1 2 3 4 5 6 { 8     1 2 3 5 6 7 { 8   1 2 3 4 5 6 7 8 9 {
               8

Каждый pаз мы беpем свеpху наименьший элемент. Таким образом, каждая операция слияния серий требует n пересылок элементов, где n - общее число элементов серий. Пусть у нас имеется N лент: N - 1 входная и одна пустая. Мы будем слиять элементы со входных лент на выходную, пока какая-либо из них не опустеет. Затем она станет входной. Пример сортировки с шестью лентами, содержащими всего 65 серий. Серии обозначены буквами fi, в таблице - количество элементов.

    Тип     f1      f2     f3     f4     f5      f6

            16      15     14     12     8
            8       7      6      4      0       8
            4       3      2      0      4       4
            2       1      0      2      2       2
            1       0      1      1      1       1
            0       1      0      0      0       0

В каждый момент времени слияние происходит на пустую ленту с остальных, поэтому число требующихся проходов приблизительно равно log N n. В данном примере распределение начальных серий побрано искусственно. Для идеальной сортировки исходные числа серий должны быть суммами n - 1 , n - 2 , ... , 1 последовательных чисел Фибоначчи порядка n - 2. Число Фибоначчи порядка p определяются следующим образом:

fi+1(p) = fi(p) + fi-1(p) + ... + fi-p(p) для i >=p,
fp(p) = 1,
fi(p) = 0 для 0 <= i < p.

чевидно, обычные числа Фибоначчи имеют порядок 1. Поэтому предположим существование фиктивных серий, таких что сумма фиктивных с реальными дает идеальное число.

Сначала все данные располагаются на одной ленте. Лента читается и отрезки распределяются по другим лентам, имеющимся в системе. после того, как созданы начальные отрезки, они сливаются, как описано выше. Один из методов, который можно использовать для создания начальных отрезков, состоит в чтении порции записей в память, их сортировке и записи результата на ленту. Выбор с замещением позволяет нам получать более длинные отрезки. Этот алгоритм работает с буфером, располагающимся в оперативной памяти. Сначала мы заполняем буфер. Затем повторяем следующие шаги до тех пор, пока не будут исчерпаны входные данные:

Hа следующей таблице выбор с замещением иллюстрируются для совсем маленького файла. Hачало файла - справа. Чтобы упростить пример, считается, что в буфер помещается всего лишь 2 записи. Конечно, в реальных задачах в буфер помещаются тысячи записей. Мы загружаем буфер на шаге В и записываем в выходной файл запись с наименьшим номером >= 6 на шаге D. Ею оказалась запись с ключом 7. Теперь мы заменяем ее на новую запись из входного файла - с ключом 4. Процесс продолжается до шага F, где мы оказывается, что последний записанный ключ равен 8 и все ключи меньше 8. В этот момент мы заканчиваем формирование текущего отрезка и начинаем формирование следующего.

                      Шаг    Вход     Буфер     Выход
                       A  5-3-4-8-6-7
                       B  5-3-4-8     6-7
                       C  5-3-4       8-7   6
                       D  5-3         8-4   7-6
                       E  5           3-4   8-7-6
                       F              5-4   3 | 8-7-6
                       G              5     4-3 | 8-7-6
                       H                    5-4-3 | 8-7-6

Обратите внимание мы храним записи в буфере до тех пор, пока не наступит время записать их в выходной файл. Если вход случаен, средняя длина отрезков равна примерно удвоенной длине буфера. Однако, если данные хоть как-то упорядочены, отрезки могут быть очень длинными. Вот почему этот метод, вообще говоря, более эффективен промежуточных, частичных сортировок. Прочитав из входного файла очередную запись, мы ищем наименьший ключ, который >= последнего считанного. При этом мы, конечно, можем просто сканировать записи в буфере. Однако, если таких записей тысячи, время поиска может оказаться недопустимо большим. Если на этом этапе использовать двоичные деревья, нам понадобится всего лишь log n сравнений.

Реализация

В реализации внешней сортировки на ANSI-C функция makeRuns вызывает readRec для чтения очередной записи. В функции readRec используется выбор с замещением (с двоичными деревьями) для получения нужной записи, а makeRuns распределяет записи согласно ряду Фибоначчи. Если количество отрезков оказывается вне последовательности Фибоначчи, в начало каждого файла добавляются пустые отрезки. Затем вызывается функция mergeSort, которая производит многофазное слияние отрезков.

/* внешняя сортировка */

#include 
#include 
#include 

/* темплейт для временных файлов (формат 8.3) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* операторы сравнения */
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y)

/* определяем сортируемые записи */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
    keyType key;                         /* ключ, по которому сортируем */
    #if LRECL
        char data[LRECL-sizeof(keyType)];       /* остальные поля */
    #endif
} recType;

typedef enum {false, true} bool;

typedef struct tmpFileTag {
    FILE *fp;                   /* указатель на файл */
    char name[LNAME];           /* имя файла */
    recType rec;                /* последняя прочитанная запись */
    int dummy;                  /* номер холостых проходов */
    bool eof;                   /* флаг конца пробега end-of-file */
    bool eor;                   /* флаг конца прохода end-of-run */
    bool valid;                 /* верно, если запись - годная */
    int fib;                    /* идеальное число Фибоначчи */
} tmpFileType;

static tmpFileType **file;      /* массив информации о временных файлах */
static int nTmpFiles;           /* количество временных файлов */
static char *ifName;            /* имя входного файла */
static char *ofName;            /* имя выходного файла */

static int level;               /* уровень проходов */
static int nNodes;              /* количество узлов для дерева выбора */

void deleteTmpFiles(void) {
    int i;

    /* удалить сливаемые файлы и освободить ресурсы */
    if (file) {
        for (i = 0; i < nTmpFiles; i++) {
            if (file[i]) {
                if (file[i]->fp) fclose(file[i]->fp);
                if (*file[i]->name) remove(file[i]->name);
                free (file[i]);
            }
        }
        free (file);
    }
}

void termTmpFiles(int rc) {

    /* очистить файлы */
    remove(ofName);
    if (rc == 0) {
        int fileT;

        /* file[T] содержит результаты */
        fileT = nTmpFiles - 1;
        fclose(file[fileT]->fp); file[fileT]->fp = NULL;
        if (rename(file[fileT]->name, ofName)) {
            perror("io1");
            deleteTmpFiles();
            exit(1);
        }
        *file[fileT]->name = 0;
    }
    deleteTmpFiles();
}

void cleanExit(int rc) {

    /* очистить временные файлы и выйти */
    termTmpFiles(rc);
    exit(rc);
}

void *safeMalloc(size_t size) {
    void *p;

    /* Безопасно выделить память и инициализоваться */
    if ((p = calloc(1, size)) == NULL) {
        printf("error: malloc failed, size = %d\n", size);
        cleanExit(1);
    }
    return p;
}

void initTmpFiles(void) {
    int i;
    tmpFileType *fileInfo;

    /* инициализовать файлы для слияния */
    if (nTmpFiles < 3) nTmpFiles = 3;
    file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
    fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
    for (i = 0; i < nTmpFiles; i++) {
        file[i] = fileInfo + i;
        sprintf(file[i]->name, FNAME, i);
        if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
            perror("io2");
            cleanExit(1);
        }
    }
}

recType *readRec(void) {

    typedef struct iNodeTag {   /* внутренний узел */
        struct iNodeTag *parent;/* предок внутреннего узла */
        struct eNodeTag *loser; /* внешний проигравший */
    } iNodeType;

    typedef struct eNodeTag {   /* внешний узел */
        struct iNodeTag *parent;/* предок внешнего узла */
        recType rec;            /* вводимая запись */
        int run;                /* номер прохода */
        bool valid;             /* вводимая запись годна */
    } eNodeType;

    typedef struct nodeTag {
        iNodeType i;            /* внутренний узел */
        eNodeType e;            /* внешний узел */
    } nodeType;

    static nodeType *node;      /* массив узлов дерева выбора */
    static eNodeType *win;      /* новый победитель */
    static FILE *ifp;           /* входной файл */
    static bool eof;            /* верно, если конец входного файла */
    static int maxRun;          /* максимальное число проходов */
    static int curRun;          /* номер текущего прохода */
    iNodeType *p;               /* указатель на внутренние узлы */
    static bool lastKeyValid;   /* верно, если lastKey годен */
    static keyType lastKey;     /* последний ключ lastKey записан */

    /* Прочитать следующую запись путем выбора с замещением */

    /* Проверка на первый выхов */
    if (node == NULL) {
        int i;

        if (nNodes < 2) nNodes = 2;
        node = safeMalloc(nNodes * sizeof(nodeType));
        for (i = 0; i < nNodes; i++) {
            node[i].i.loser = &node[i].e;
            node[i].i.parent = &node[i/2].i;
            node[i].e.parent = &node[(nNodes + i)/2].i;
            node[i].e.run = 0;
            node[i].e.valid = false;
        }
        win = &node[0].e;
        lastKeyValid = false;

        if ((ifp = fopen(ifName, "rb")) == NULL) {
            printf("error: file %s, unable to open\n", ifName);
            cleanExit(1);
        }
    }

    while (1) {

        /* заместить предыдущего победителя новой записью */
        if (!eof) {
            if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
                if ((!lastKeyValid || compLT(win->rec.key, lastKey))
                && (++win->run > maxRun))
                    maxRun = win->run;
                win->valid = true;
            } else if (feof(ifp)) {
                fclose(ifp);
                eof = true;
                win->valid = false;
                win->run = maxRun + 1;
            } else {
                perror("io4");
                cleanExit(1);
            }
        } else {
            win->valid = false;
            win->run = maxRun + 1;
        }

        /* привести в порядок предков победителя и проигравшего */
        p = win->parent;
        do {
            bool swap;
            swap = false;
            if (p->loser->run < win->run) {
                swap = true;
            } else if (p->loser->run == win->run) {
                if (p->loser->valid && win->valid) {
                    if (compLT(p->loser->rec.key, win->rec.key))
                        swap = true;
                } else {
                    swap = true;
                }
            }
            if (swap) {
                /* p должно быть победителем */
                eNodeType *t;

                t = p->loser;
                p->loser = win;
                win = t;
            }
            p = p->parent;
        } while (p != &node[0].i);

        /* конец прохода ? */
        if (win->run != curRun) {
            /* win->run = curRun + 1 */
            if (win->run > maxRun) {
                /* конец вывода */
                free(node);
                return NULL;
            }
            curRun = win->run;
        }

        /* вывести верх дерева */
        if (win->run) {
            lastKey = win->rec.key;
            lastKeyValid = true;
            return &win->rec;
        }
    }
}

void makeRuns(void) {
    recType *win;       /* победитель */
    int fileT;          /* прошлый файл */
    int fileP;          /* следующий за прошлым файлом  */
    int j;              /* выбираем file[j] */


    /* Сделать инициализационные проходы через выбор с замещением.
     * Проходы напианы с использованием распределения Фибоначчи.
     */

    /* инициализовать файловые структуры */
    fileT = nTmpFiles - 1;
    fileP = fileT - 1;
    for (j = 0; j < fileT; j++) {
        file[j]->fib = 1;
        file[j]->dummy = 1;
    }
    file[fileT]->fib = 0;
    file[fileT]->dummy = 0;

    level = 1;
    j = 0;


    win = readRec();
    while (win) {
        bool anyrun;

        anyrun = false;
        for (j = 0; win && j <= fileP; j++) {
            bool run;

            run = false;
            if (file[j]->valid) {
                if (!compLT(win->key, file[j]->rec.key)) {
                    /* добавить к существующему проходу */
                    run = true;
                } else if (file[j]->dummy) {
                    /* начать новый проход */
                    file[j]->dummy--;
                    run = true;
                }
            } else {
                /* первый проход в файле */
                file[j]->dummy--;
                run = true;
            }

            if (run) {
                anyrun = true;

                /* полный проход */
                while(1) {
                    if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
                        perror("io3");
                        cleanExit(1);
                    }
                    file[j]->rec.key = win->key;
                    file[j]->valid = true;
                    if ((win = readRec()) == NULL) break;
                    if (compLT(win->key, file[j]->rec.key)) break;
                }
            }
        }

        /* Если нет места для проходов - вверх на уровень */
        if (!anyrun) {
            int t;
            level++;
            t = file[0]->fib;
            for (j = 0; j <= fileP; j++) {
                file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
                file[j]->fib = t + file[j+1]->fib;
            }
        }
    }
}

void rewindFile(int j) {
    /* Идти в начало file[j] и читать первую запись */
    file[j]->eor = false;
    file[j]->eof = false;
    rewind(file[j]->fp);
    if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
        if (feof(file[j]->fp)) {
            file[j]->eor = true;
            file[j]->eof = true;
        } else {
            perror("io5");
            cleanExit(1);
        }
    }
}

void mergeSort(void) {
    int fileT;
    int fileP;
    int j;
    tmpFileType *tfile;

    /* Многофазная сортировка слиянием */

    fileT = nTmpFiles - 1;
    fileP = fileT - 1;

    /* снабдить файлы информацией */
    for (j = 0; j < fileT; j++) {
        rewindFile(j);
    }

    /* Каждый проход по циклу сливает один проход */
    while (level) {
        while(1) {
            bool allDummies;
            bool anyRuns;

            /* сканировать на предмет проходов */
            allDummies = true;
            anyRuns = false;
            for (j = 0; j <= fileP; j++) {
                if (!file[j]->dummy) {
                    allDummies = false;
                    if (!file[j]->eof) anyRuns = true;
                }
            }

            if (anyRuns) {
                int k;
                keyType lastKey;

                /* слить 1 проход file[0]..file[P] --> в file[T] */

                while(1) {
                   /* Каждый проход по циклу записывает 1 запись в file[fileT]
*/

                    /* Hайти наименьший ключ */
                    k = -1;
                    for (j = 0; j <= fileP; j++) {
                        if (file[j]->eor) continue;
                        if (file[j]->dummy) continue;
                        if (k < 0 ||
                        (k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
                            k = j;
                    }
                    if (k < 0) break;

                    /* записать record[k] в file[fileT] */
                    if (fwrite(&file[k]->rec, sizeof(recType), 1,
                            file[fileT]->fp) != 1) {
                        perror("io6");
                        cleanExit(1);
                    }

                    /* заменить record[k] */
                    lastKey = file[k]->rec.key;
                    if (fread(&file[k]->rec, sizeof(recType), 1,
                            file[k]->fp) == 1) {
                        /* проверить на предмет конца пробега file[s] */
                        if (compLT(file[k]->rec.key, lastKey))
                            file[k]->eor = true;
                    } else if (feof(file[k]->fp)) {
                        file[k]->eof = true;
                        file[k]->eor = true;
                    } else {
                        perror("io7");
                        cleanExit(1);
                    }
                }

                /* Подкорректировкать холостые */
                for (j = 0; j <= fileP; j++) {
                    if (file[j]->dummy) file[j]->dummy--;
                    if (!file[j]->eof) file[j]->eor = false;
                }

            } else if (allDummies) {
                for (j = 0; j <= fileP; j++)
                    file[j]->dummy--;
                file[fileT]->dummy++;
            }

            /* конец прохода */
            if (file[fileP]->eof && !file[fileP]->dummy) {
                /* completed a fibonocci-level */
                level--;
                if (!level) {
                    /* готово, file[fileT] содержит данные */
                    return;
                }

                /* fileP истощился, открываем новый такой же */
                fclose(file[fileP]->fp);
                if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
                        == NULL) {
                    perror("io8");
                    cleanExit(1);
                }
                file[fileP]->eof = false;
                file[fileP]->eor = false;

                rewindFile(fileT);

                /* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
                tfile = file[fileT];
                memmove(file + 1, file, fileT * sizeof(tmpFileType*));
                file[0] = tfile;

                /* начать новые проходы */
                for (j = 0; j <= fileP; j++)
                    if (!file[j]->eof) file[j]->eor = false;
            }
        }

    }
}


void extSort(void) {
    initTmpFiles();
    makeRuns();
    mergeSort();
    termTmpFiles(0);
}

int main(int argc, char *argv[]) {

    /* командная строка:
     *
     *   ext ifName ofName nTmpFiles nNodes
     *
     *   ext in.dat out.dat 5 2000
     *       читает in.dat, сортирует, используя 5 файлов и 2000 узлов,
     *        выводит в out.dat
     */
    if (argc != 5) {
        printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
        cleanExit(1);
    }

    ifName = argv[1];
    ofName = argv[2];
    nTmpFiles = atoi(argv[3]);
    nNodes = atoi(argv[4]);

    printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
        nTmpFiles, nNodes, sizeof(recType));

    extSort();

    return 0;
}