{
  Описание всех алгоритмов можно найти в книге:
      Кнут Д., Искусство программирования для ЭВМ, Т. 3.:
        Сортировка и поиск. М.: Мир, 1978.
  Описание почти всех алгоритмов в книге:
      Кормен Т., Лейзерсон Ч., Ривест Р., Алгоритмы:
        построение и анализ. М.: МЦНМО, 1999.
  Описание некоторых алгоритмов в книге:
      Романовский И., Дискретный анализ,
        СПб.: Невский диалект, 1999.
}
 
program SORT_ARRAY;
 
{ Увеличение размера стека - нужно для рекурсивных алгоритмов
  MergeSort и QuickSort }
{$M 65520, 0, 655360}
 
  { Необязательно, но используется при подсчете времени }
  uses Crt;
 
  const
    { Размер массива }
    max = 16000;
    { Диапазон случайных чисел }
    randmax : Longint = 16000000;
    theword : Longint = 65536;
 
 
  type
    { Тип элемента сортируемого массива }
    itp = Longint;
    { Тип массива }
    mas = array [0..max] of itp;
    { Тип процедуры для сортировки или заполнения массива }
    Func = procedure ( var A : mas );
    { Массивы для цифровой сортировки и сортировки вычерпыванием }
    C8T = array [0..256] of Integer;
    C12T = array [0..4096] of Integer;
 
{ Необходимая директива для использования переменных типа процедуры }
{$F+}
 
  { Заполнение массива числами по возрастанию }
  procedure FillInc( var A : mas );
    var
      i : Integer;
    begin
      for i := 1 to max do
        A[i] := i;
    end;
 
  { Заполнение массива числами по убыванию }
  procedure FillDec( var A : mas );
    var
      i : Integer;
    begin
      for i := 1 to max do
        A[i] := max - i;
    end;
 
  { Заполнение массива равными числами (0) }
  procedure FillZero( var A : mas );
    var
      i : Integer;
    begin
      for i := 1 to max do
        A[i] := 0;
    end;
 
  { Заполнение массива случайными числами }
  procedure FillRand( var A : mas );
    var
      i : Integer;
      t : LongInt;
    begin
      for i := 1 to max do
        begin
          t := Random(32768);
          t := t * 32768;
          t := t + Random(32768);
          A[i] := t mod randmax;
        end;
    end;
 
  { Сортировка вставками }
  procedure InsertSort( var A : mas );
    var
      i, k : Integer;
      x : itp;
    begin
      { Вставляем в уже отсортированную часть элементы со 2 по max }
      for i := 2 to max do
        begin
          k := i;
          x := A[i];
          { Передвигаем на 1 позицию направо элементы,
            большие вставляемого элемента (он записан в x) }
          { Условие k > 1 гарантирует, что мы не выйдем за
            границу массива, если вставляется элемент,
            меньший всех предыдущих.
            В Turbo Pascal условия вычисляются в обратном порядке,
            поэтому условие цикла while нужно заменить на
            (A[k - 1] > x) and (k > 1) }
          while (k > 1) and (A[k - 1] > x) do
            begin
              A[k] := A[k - 1];
              k := k - 1;
            end;
          { Вставляем элемент в нужную позицию }
          A[k] := x;
        end;
    end;
 
  { Сортировка вставками с ограничителем }
  procedure InsertSort2( var A : mas );
    var
      i, k : Integer;
      x : itp;
    begin
      { Вставляем ограничитель, меньший каждого элемента массива }
      A[0] := -1;
      { Вставляем в уже отсортированную часть элементы со 2 по max }
      for i := 2 to max do
        begin
          k := i;
          x := A[i];
          { Передвигаем на 1 позицию направо элементы,
            большие вставляемого элемента (он записан в x) }
          { Здесь не нужно проверять k > 1, так как есть ограничитель
            и всегда будет A[0] < x }
          while A[k - 1] > x do
            begin
              A[k] := A[k - 1];
              k := k - 1;
            end;
          { Вставляем элемент в нужную позицию }
          A[k] := x;
        end;
    end;
 
  { Сортировка выбором без запоминания минимума }
  procedure SelectSort( var A : mas );
    var
      i, j, m : Integer;
      x : itp;
    begin
      { Ищем элементы для позиций с 1 по max - 1 }
      for i := 1 to max - 1 do
        begin
          m := i;
          { Просматриваем все еще не выбранные элементы }
          for j := i + 1 to max do
            { Если встречается элемент, меньший того, что сейчас
              стоит на позиции m, запоминаем в m его позицию  }
            if A[j] < A[m] then
              m := j;
          { Меняем местами i-ый элемент и минимальный из оставшихся -
            m-ый элемент }
          x := A[i];
          A[i] := A[m];
          A[m] := x;
        end;
    end;
 
  { Сортировка выбором }
  procedure SelectSort2(var A : mas);
    var
      i, j, m : Integer;
      x : itp;
    begin
      { Ищем элементы для позиций с 1 по max - 1 }
      for i := 1 to max - 1 do
        begin
          m := i;
          x := A[i];
          { Просматриваем все еще не выбранные элементы }
          for j := i + 1 to max do
            { Если встречается элемент, меньший того, что сейчас
              стоит на позиции m, запоминаем в m его позицию,
              а в x - его значение }
            if x > A[j] then
              begin
                m := j;
                x := A[j];
              end;
            { Меняем местами i-ый элемент, и минимальный из оставшихся -
              m-ый элемент, сохраненный в x }
            A[m] := A[i];
            A[i] := x;
        end;
    end;
 
  { Сортировка "пузырьком" }
  procedure BubbleSort( var A : mas );
    var
      i, j : Integer;
      x : itp;
    begin
      for i := max downto 2 do
        for j := 2 to i do
          if A[j] < A[j - 1] then
            begin
              x := A[j];
              A[j] := A[j - 1];
              A[j - 1] := x;
            end;
    end;
 
  { Сортировка "шейкером" }
  procedure ShakerSort( var A : mas );
    var
      l, r, j : Integer;
      x : itp;
    begin
      l := 2;
      r := max;
      while l <= r do
        begin
          { "Пузырек" слева направо }
          for j := l to r do
          if A[j] < A[j - 1] then
            begin
              x := A[j];
              A[j] := A[j - 1];
              A[j - 1] := x;
            end;
          r := r - 1;
          { "Пузырек" справа налево }
          for j := r downto l do
          if A[j] < A[j - 1] then
            begin
              x := A[j];
              A[j] := A[j - 1];
              A[j - 1] := x;
            end;
          l := l + 1;
        end;
    end;
 
  { Сортировка "пузырьком" с остановкой }
  procedure BubbleSort2( var A : mas );
    var
      i, j, n : Integer;
      x : itp;
    begin
      i := max;
      n := 1;
      { Пока производились обмены элементов }
      while n > 0 do
        begin
          n := 0;
          for j := 2 to i do
            if A[j] < A[j - 1] then
              begin
                x := A[j];
                A[j] := A[j - 1];
                A[j - 1] := x;
                n := 1;
              end;
          i := i - 1;
        end;
    end;
 
  { Сортировка Шелла }
  procedure ShellSort( var A : mas );
    const
      steps = 12;
    var
      i, j, l, k, p, n : Integer;
      x : itp;
      s : array [1..steps] of Integer;
    begin
      k := 1;
      { Формируем последовательность чисел -
        шаги, с которыми выбираем сортируемые подмассивы }
      for i := steps downto 1 do
        begin
          s[i] := k;
          k := k * 2 + 1;
        end;
 
      { Сортировки подмассивов вплоть до шага 1 -
        обычной сортировки пузырьком }
      for k := 1 to steps do
        begin
          l := s[k];
          { Для каждого шага l нужно отсортировать l подмассивов }
          for p := 1 to l do
            begin
              i := max - l;
              n := 1;
              { Сортировка подмассива пузырьком с остановкой }
              { Подмассив - это (A[p], A[p+l], A[p+2*l], ...) }
              while n > 0 do
                begin
                  n := 0;
                  j := p;
                  while j <= i do
                    begin
                      if A[j] > A[j + l] then
                        begin
                          x := A[j];
                          A[j] := A[j + l];
                          A[j + l] := x;
                          n := 1;
                        end;
                      j := j + l;
                    end;
                  i := i - l;
                end;
            end;
        end;
    end;
 
  { Объединение двух массивов для сортировки слиянием }
  procedure Merge( var A, P : mas; l, m, r : Integer );
    var
      i, j, k, z : Integer;
      A2 : mas;
    begin
      z := r - l + 1;
      i := l;
      j := m;
      k := 1;
      { Пока на "слили" все элементы от l до r }
      while k <= z do
        begin
          { Элемент из первого массива меньше или
            во втором массиве закончились элементы }
          if (j > r) or ((i < m) and (A[i] < A[j])) then
            begin
              A2[k] := A[i];
              i := i + 1;
            end
          { Элемент из второго массива меньше или
            в первом массиве закончились элементы }
          else
            begin
              A2[k] := A[j];
              j := j + 1;
            end;
          k := k + 1;
        end;
      i := l;
      { Копируем слитые элементы обратно в массив A }
      for k := 1 to z do
        begin
          A[i] := A2[k];
          i := i + 1;
        end;
    end;
 
  { Процедура рекурсивной сортировки слиянием }
  procedure RecoursiveMerge(var A, P : mas; l, r : Word);
    var
      m : Integer;
    begin
      m := (l + r + 1) div 2;
      { Сортируем первую половину }
      if l < m then
        RecoursiveMerge(A, P, l, m - 1);
      { Сортируем вторую половину }
      if m < r then
        RecoursiveMerge(A, P, m, r);
      { Сливаем два отсортированных массива }
      Merge(A, P, l, m, r);
    end;
 
  { Сортировка слиянием }
  procedure MergeSort( var A : mas );
    var
      p : ^mas;
    begin
      New(p);
      RecoursiveMerge(A, p^, 1, max);
      Dispose(p);
    end;
 
  { Процедура рекурсивной сортировки слиянием с подсортировкой }
  procedure RecoursiveMerge2(var A, P : mas; l, r, b : Word);
    var
      i, k, m : Integer;
      x : itp;
    begin
      { Если количество элементов в сортируемом массиве меньше b,
        сортируем его вставками }
      if r - l < b then
        begin
          for i := l + 1 to r do
            begin
              k := i;
              x := A[i];
              while (k > l) and (A[k - 1] > x) do
                begin
                  A[k] := A[k - 1];
                  k := k - 1;
                end;
              A[k] := x;
            end;
        end
      { Если количество элементов в сортируемом массиве больше b,
        делим его на две половины, сортируем их и затем сливаем }
      else
        begin
          m := (l + r) div 2;
          RecoursiveMerge2(A, P, l, m - 1, b);
          RecoursiveMerge2(A, P, m, r, b);
          Merge(A, P, l, m, r);
        end;
    end;
 
  { Сортировка слиянием с подсортировкой вставками по 10 элементов }
  procedure MergeSort10( var A : mas );
    var
      p : ^mas;
    begin
      New(p);
      RecoursiveMerge2(A, p^, 1, max, 10);
      Dispose(p);
    end;
 
  { Сортировка слиянием с подсортировкой вставками по 100 элементов }
  procedure MergeSort100( var A : mas );
    var
      p : ^mas;
    begin
      New(p);
      RecoursiveMerge2(A, p^, 1, max, 100);
      Dispose(p);
    end;
 
  { Сортировка слиянием с подсортировкой вставками по 1000 элементов }
  procedure MergeSort1000( var A : mas );
    var
      p : ^mas;
    begin
      New(p);
      RecoursiveMerge2(A, p^, 1, max, 1000);
      Dispose(p);
    end;
 
  { Процедура разбиения массива для быстрой сортировки }
  function Partition( var A : mas; l, r : Integer; x : itp ) : Integer;
  { Переставляем элементы массива так, чтобы слева от элемента,
    равного x, были только элементы меньшие или равные x,
    а справа - элементы, большие или равные x }
    var
      i, j : Integer;
      t : itp;
    begin
      i := l - 1;
      j := r + 1;
      repeat
 
        { Пока элементы справа больше среднего }
        repeat
          j := j - 1;
        until x >= A[j];
 
        { Пока элементы слева меньше среднего }
        repeat
          i := i + 1;
        until A[i] >= x;
 
        { Меняем левый и правый элементы и продолжаем дальше }
        if i < j then
          begin
            t := A[i];
            A[i] := A[j];
            A[j] := t;
          end;
        { Иначе - левый и правый встретились -
          разбиение массива завершено }
 
      until i >= j;
      Partition := j;
    end;
 
  { Рекурсивная процедура быстрой сортировки }
  procedure RecoursiveQuick( var A : mas; l, r : Integer );
    var
      m : Integer;
    begin
      if l < r then
        begin
          { В качестве граничного элемента выбирается средний
            элемент массива }
          m := Partition(A, l, r, A[(l + r) div 2]);
          RecoursiveQuick(A, l, m);
          RecoursiveQuick(A, m + 1, r);
        end;
    end;
 
  { Быстрая сортировка }
  procedure QuickSort( var A : mas );
    begin
      RecoursiveQuick(A, 1, max);
    end;
 
  { Рекурсивная процедура рандомизированной быстрой сортировки }
  procedure RecoursiveRandomQuick( var A : mas; l, r : Integer );
    var
      m : Integer;
    begin
      if l < r then
        begin
          { В качестве граничного элемента выбирается элемент
            массива со случайным номером }
          m := Partition(A, l, r, A[Random(r - l + 1) + l]);
          RecoursiveRandomQuick(A, l, m);
          RecoursiveRandomQuick(A, m + 1, r);
        end;
    end;
 
  { Рандомизированная быстрая сортировка }
  procedure RandomQuickSort( var A : mas );
    begin
      RecoursiveRandomQuick(A, 1, max);
    end;
 
  { Рекурсивная процедура быстрой сортировки с выбором медианы }
  procedure RecoursiveMedianQuick( var A : mas; l, r : Integer );
    var
      m : Integer;
      x1, x2, x3 : itp;
    begin
      if l < r then
        begin
          { В качестве граничного элемента выбирается средний
            по величине элемент из трех }
          x1 := A[l + (r - l + 1) div 4];
          x2 := A[(l + r) div 2];
          x3 := A[Integer(l + Longint(r - l + 1) * 3 div 4)];
          if x1 < x2 then
            begin
              if x3 < x2 then
                begin
                  if x1 < x3 then
                    x2 := x3
                  else
                    x2 := x1
                end
            end
          else { x1 > x2 }
            begin
              if x3 > x2 then
                begin
                  if x1 > x3 then
                    x2 := x3
                  else
                    x2 := x1
                end
            end;
 
          m := Partition(A, l, r, x2);
          RecoursiveMedianQuick(A, l, m);
          RecoursiveMedianQuick(A, m + 1, r);
        end;
    end;
 
  { Быстрая сортировка с выбором медианы по 3 элементам }
  procedure MedianQuickSort( var A : mas );
    begin
      RecoursiveMedianQuick(A, 1, max);
    end;
 
  { Исправление кучи с неправильным элементом в вершине }
  procedure HeapCorrect( var A : mas; Bound, n : Integer );
  { Перестановка элементов упорядоченной кучи, на вершине
    которой - единственный неупорядоченный элемент так,
    чтобы куча снова стала упорядоченной }
    var
      l, r, i : Integer;
      x : itp;
    begin
      { n - вершина кучи }
      { l - левый ребенок вершины, r - правый ребенок }
      l := n * 2;
      r := l + 1;
 
      { В i - номер максимального элемента из n, l и r }
      i := n;
      if r <= Bound then
        begin
          if A[l] > A[i] then
            i := l;
          if A[r] > A[i] then
            i := r;
        end
      else if l <= Bound then
        begin
          if A[l] > A[i] then
            i := l;
        end;
 
      { Если максимальный элемент не в вершине,
        меняем максимальный элемент с вершиной и
        вызываем HeapCorrect для подкучи, на вершину которой
        попал элемент из вершины }
      if i <> n then
        begin
          x := A[i];
          A[i] := A[n];
          A[n] := x;
          HeapCorrect(A, Bound, i);
        end;
    end;
 
  { Сортировка при помощи кучи }
  procedure HeapSort( var A : mas );
    var
      i, Bound : Integer;
      x : itp;
    begin
      { Строим упорядоченную кучу }
      for i := (max + 1) div 2 downto 1 do
        HeapCorrect(A, max, i);
 
      Bound := max;
      while Bound > 1 do
        begin
          { Меняем последний элемент кучи с максимальным
            элементом в вершине кучи }
          x := A[1];
          A[1] := A[Bound];
          A[Bound] := x;
          { Уменьшаем размер кучи }
          Bound := Bound - 1;
          { Упорядочиваем кучу }
          HeapCorrect(A, Bound, 1);
        end;
    end;
 
  { Сортировка подсчетом по n-ой 256-ричной цифре }
  procedure Counting8Sort( var A : mas; n: Integer );
    var
      i, j, k, s, index : Integer;
      P : ^mas;
      C : C8T;
    begin
      { Вычисляем сдвиг для n-ой цифры }
      s := 8 * n;
 
      New(P);
 
      { Обнуляем массив частот }
      for i := 0 to 255 do
        C[i] := 0;
 
      { Считаем частоты появления всех цифр в n-ой позиции }
      { Заодно копируем массив A в P^ }
      for i := 1 to max do
        begin
          { index - это значение n-ой цифры }
          index := (A[i] shr s) and 255;
          C[index] := C[index] + 1;
          P^[i] := A[i];
        end;
 
      { Сейчас в каждом C[i] - количество элементов массива A,
        у которых n-ая цифра равна i }
      { После следующего цикла в каждом C[i] будет записано
        количество элементов, с n-ой цифрой, не превосходящей i,
        а это то же самое, что номер последнего элемента
        с n-ой цифрой, равной i }
      for i := 1 to 255 do
        C[i] := C[i] + C[i - 1];
 
      { Переписываем элементы из массива P^ в A, начиная с последнего,
        в соответствии с номерами, записанными в C. Номер последнего
        элемента с n-ой цифрой, равной i, - C[i] - после записи
        элемента в позицию C[i] уменьшаем на 1 }
      for i := max downto 1 do
        begin
          index := (P^[i] shr s) and 255;
          A[C[index]] := P^[i];
          C[index] := C[index] - 1;
        end;
 
      Dispose(P);
    end;
 
  { Цифровая сортировка для 8-разрядных цифр }
  procedure Digital8Sort( var A : mas );
    var
      n : Integer;
      t : itp;
    begin
      t := randmax;
      n := 0;
      { Сортировка по всем цифрам, начиная с последней }
      while t > 0 do
        begin
          Counting8Sort(A, n);
          n := n + 1;
          t := t shr 8;
        end;
    end;
 
  { Сортировка подсчетом по n-ой 4096-ричной цифре }
  procedure Counting12Sort( var A : mas; n: Integer );
    var
      i, j, k, index : Integer;
      P : ^mas;
      C : C12T;
      s : Longint;
      bug : Integer;
    begin
      { Вычисляем сдвиг для n-ой цифры }
      s := 12 * n;
 
      { Переменная bug используется вместо числа 4095 -
        в общем случае это неверно, но таким образом
        обходится ошибка в Borland Pascal, где
        неправильно выполняется операция x shr 24 }
      if s = 24 then
        bug := 255
      else
        bug := 4095;
 
      New(P);
 
      { Обнуляем массив частот }
      for i := 0 to 4095 do
        C[i] := 0;
 
      { Считаем частоты появления всех цифр в n-ой позиции }
      { Заодно копируем массив A в P^ }
      for i := 1 to max do
        begin
          { index - это значение n-ой цифры }
          index := (A[i] shr s) and bug;
          C[index] := C[index] + 1;
          P^[i] := A[i];
        end;
 
      { Сейчас в каждом C[i] - количество элементов массива A,
        у которых n-ая цифра равна i }
      { После следующего цикла в каждом C[i] будет записано
        количество элементов, с n-ой цифрой, не превосходящей i,
        а это то же самое, что номер последнего элемента
        с n-ой цифрой, равной i }
      for i := 1 to 4095 do
        C[i] := C[i] + C[i - 1];
 
      { Переписываем элементы из массива P^ в A, начиная с последнего,
        в соответствии с номерами, записанными в C. Номер последнего
        элемента с n-ой цифрой, равной i, - C[i] - после записи
        элемента в позицию C[i] уменьшаем на 1 }
      for i := max downto 1 do
        begin
          index := (P^[i] shr s) and bug;
          A[C[index]] := P^[i];
          C[index] := C[index] - 1;
        end;
 
      Dispose(P);
    end;
 
  { Цифровая сортировка для 12-разрядных цифр }
  procedure Digital12Sort( var A : mas );
    var
      n : Integer;
      t : itp;
    begin
      t := randmax;
      n := 0;
      { Сортировка по всем цифрам, начиная с последней }
      while t > 0 do
        begin
          Counting12Sort(A, n);
          n := n + 1;
          t := t shr 12;
        end;
    end;
 
  { Сортировка вычерпыванием по 256 частям }
  procedure Bucket8Sort( var A : mas );
    var
      i, index, j, k : Integer;
      d, x : itp;
      P : ^mas;
      C : C8T;
    begin
      { Определяем размер каждой части }
      d := (randmax div 256) + 1;
 
      New(P);
 
      { Определяем количества элементов массива A,
        попадающих в каждую часть -
        так же, как в цифровой сортировке }
      for i := 0 to 256 do
        C[i] := 0;
      for i := 1 to max do
        begin
          index := A[i] div d;
          C[index] := C[index] + 1;
          P^[i] := A[i];
        end;
      for i := 1 to 256 do
        C[i] := C[i] + C[i - 1];
 
      { Переписываем элементы массива так, что сначала идут
        элементы, попавшие в первую часть, затем - элементы
        из второй части }
      for i := max downto 1 do
        begin
          index := P^[i] div d;
          A[C[index]] := P^[i];
          C[index] := C[index] - 1;
        end;
 
      { Остается только отсортировать элементы внутри каждой части -
        используем для этого сортировку вставками }
      for i := 0 to 255 do
        begin
          for j := C[i] + 2 to C[i + 1] do
            begin
              k := j;
              x := A[j];
              while (k > C[i] + 1) and (A[k - 1] > x) do
                begin
                  A[k] := A[k - 1];
                  k := k - 1;
                end;
              A[k] := x;
            end;
        end;
 
      Dispose(P);
  end;
 
  { Сортировка вычерпыванием по 4096 частям }
  procedure Bucket12Sort( var A : mas );
    var
      i, index, j, k : Integer;
      d, x : itp;
      P : ^mas;
      C : C12T;
    begin
      { Определяем размер каждой части }
      d := (randmax div 4096) + 1;
 
      New(P);
 
      { Определяем количества элементов массива A,
        попадающих в каждую часть -
        так же, как в цифровой сортировке }
      for i := 0 to 4096 do
        C[i] := 0;
      for i := 1 to max do
        begin
          index := A[i] div d;
          C[index] := C[index] + 1;
          P^[i] := A[i];
        end;
      for i := 1 to 4096 do
        C[i] := C[i] + C[i - 1];
 
      { Переписываем элементы массива так, что сначала идут
        элементы, попавшие в первую часть, затем - элементы
        из второй части }
      for i := max downto 1 do
        begin
          index := P^[i] div d;
          A[C[index]] := P^[i];
          C[index] := C[index] - 1;
        end;
 
      { Остается только отсортировать элементы внутри каждой части -
        используем для этого сортировку вставками }
      for i := 0 to 4095 do
        begin
          for j := C[i] + 2 to C[i + 1] do
            begin
              k := j;
              x := A[j];
              while (k > C[i] + 1) and (A[k - 1] > x) do
                begin
                  A[k] := A[k - 1];
                  k := k - 1;
                end;
              A[k] := x;
            end;
        end;
 
      Dispose(P);
  end;
 
{$F-}
 
  { Проверка того, что массив отсортирован }
  function CheckArray( var A : mas ) : Boolean;
    var
      i : Integer;
    begin
      CheckArray := TRUE;
      for i := 1 to max - 1 do
        if A[i] > A[i + 1] then
          CheckArray := FALSE;
    end;
 
  { Вывод элементов массива на экран }
  procedure PrintArray( var A : mas );
    var
      i : Integer;
    begin
      WriteLn;
      for i := 1 to max do
        Write(A[i] : 16);
      WriteLn;
    end;
 
  var
    A : mas;
    Fill  : array [1..4] of Func;
    FillS : array [1..4] of string[24];
    Sort  : array [1..20] of Func;
    SortS : array [1..20] of string[24];
    i, j : Integer;
    Time : Longint;
  begin
    FillS[1] := 'Random';
    FillS[2] := 'Increasing';
    FillS[3] := 'Equal';
    FillS[4] := 'Decreasing';
    Fill[1] := FillRand;
    Fill[2] := FillInc;
    Fill[3] := FillZero;
    Fill[4] := FillDec;
    SortS[1] := 'Insertion';
    SortS[2] := 'Insertion with Bound';
    SortS[3] := 'Selection (ver. 1)';
    SortS[4] := 'Selection';
    SortS[5] := 'Bubble';
    SortS[6] := 'Stopping Bubble';
    SortS[7] := 'Shaker';
    SortS[8] := 'Shell';
    SortS[9] := 'Merge';
    SortS[10] := 'Merge + Insertion 10';
    SortS[11] := 'Merge + Insertion 100';
    SortS[12] := 'Merge + Insertion 1000';
    SortS[13] := 'Quick';
    SortS[14] := 'Randomized Quick';
    SortS[15] := 'Median Quick';
    SortS[16] := 'Heap';
    SortS[17] := 'Digital - 8';
    SortS[18] := 'Digital - 12';
    SortS[19] := 'Bucket - 256';
    SortS[20] := 'Bucket - 4096';
    Sort[1] := InsertSort;
    Sort[2] := InsertSort2;
    Sort[3] := SelectSort;
    Sort[4] := SelectSort2;
    Sort[5] := BubbleSort;
    Sort[6] := BubbleSort2;
    Sort[7] := ShakerSort;
    Sort[8] := ShellSort;
    Sort[9] := MergeSort;
    Sort[10] := MergeSort10;
    Sort[11] := MergeSort100;
    Sort[12] := MergeSort1000;
    Sort[13] := QuickSort;
    Sort[14] := RandomQuickSort;
    Sort[15] := MedianQuickSort;
    Sort[16] := HeapSort;
    Sort[17] := Digital8Sort;
    Sort[18] := Digital12Sort;
    Sort[19] := Bucket8Sort;
    Sort[20] := Bucket12Sort;
 
    Write('' : 24);
    for i := 1 to 4 do
      Write(FillS[i] : 12);
    WriteLn;
    for i := 1 to 20 do
      begin
        Write(SortS[i] : 24);
        for j := 1 to 4 do
          begin
            Fill[j](A);
            Time := Meml[$40 : $6C];
            Sort[i](A);
            Time := Meml[$40 : $6C] - Time;
            if CheckArray(A) then
              Write(Time : 12)
            else
              begin
                Write('Failed' : 12);
{                PrintArray(A);}
              end;
          end;
        WriteLn;
      end;
  end.