В 1959 г. Д.Шеллом было предложено усовершенствование сортировки с помощью прямого включения. 

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

Например: Дан массив, состоящий из элементов: 

44  55  12  42  94  18  06  67

44  18  06  42  94  55 12  67

06  18  12  42  44  55  94  67

06  12  18  42  44  55  67  94

Ясно, что такой метод в результате дает упорядоченный массив, и, конечно же, сразу видно, что каждый проход от предыдущих только выигрывает (так как каждая i-сортировка объединяет две группы, уже отсортированные 2i-сортировкой). Так же очевидно, что расстояния в группах можно уменьшать по-разному, лишь бы последнее было единичным, ведь в самом плохом случае последний проход и сделает всю работу. Все t расстояния обозначаются соответственно h₁,h₂,...,h_t, для них выполняются условия 

h_t=1, h_i+1<h_i

Анализ этого алгоритма поставил несколько проблем. Не известно, какие расстояния дают наилучшие результаты. Д.Кнут в работе ╚Искусство программирования для ЭВМ╩ показывает, что имеет смысл использовать такую последовательность ( записана в обратном порядке): 

1, 4, 13, 40, 121, ...  или  1, 3, 7, 15, 31, ...

Метод сортировки с помощью прямого выбора основан на повторяющихся поисках наименьшего ключа среди n элементов, среди оставшихся n-1 элементов и т.д. Обнаружение наименьшего среди n элементов требует - это очевидно - n-1 сравнения, среди n-1 нужно n-2 сравнений и т.д. Сумма первых n-1 целых равна 1/2(n²-n). Как же в таком случае можно усовершенствовать упомянутый метод сортировки? Этого можно добиться, только оставляя после каждого прохода больше информации, чем просто идентификация единственного минимального элемента. Например, сделав n/2 сравнений, можно определить в каждой паре ключей меньший. С помощью n/4 сравнений - меньший из пары уже выбранных меньших и т.д. Проделав n-1 сравнений, мы можем построить дерево выбора и идентифицировать его корень как нужный нам наименьший ключ. 
Рассмотрим тот же массив:  44  55  12  42  94  18  06  67. Из двух соседних будем выбирать наименьший. 

Повторяющиеся выборы среди двух ключей. 

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

                      12                                                                     ? 
  

         44                      12                                    18                              ? 

44            55        12           42                    94             18            ?                 67

                                                           12 
 
  

                      12                                                                   18 
  

         44                      12                                    18                              67 

44            55        12           42                    94             18               ?             67 

Заполнение дырок. 

Элемент, передвинувшийся в корень дерева, вновь будет наименьшим (теперь уже вторым) ключом, и его можно исключить. После n таких шагов дерево станет пустым (т.е. в нем останутся только дырки), и процесс сортировки заканчивается. Обратите внимание - на каждом из n шагов выбора требуется только n·logn элементарных операций плюс еще n шагов на построение дерева. Это весьма существенное улучшение. Естественно, сохранение дополнительной информации делает задачу более изощренной, поэтому в сортировке по дереву каждый отдельный шаг усложняется. Наша следующая задача - найти приемы эффективной организации этой информации. Это удалось добиться в методе Heapsort, изобретенном Д.Уилльямсом. 

Пирамида определяется как последовательность ключей h_L, h_L+1,...,h_R, такая, что 
hi<=h_2i и hi<=h_2i+1 для i=L...R/2. 
                                                               h₁ 

                      h₂                                                                    h₃ 

         h₄                       h₅                                        h₆                          h₇ 

 h₈            h₉        h₁₀           h₁₁                    h₁₂               h₁₃       h₁₄            h₁₅ 

Предположим, есть некоторая пирамида с заданными элементами h_L+1,...,h_R для некоторых значений L и R и нужно добавить новый элемент x, образуя расширенную пирамиду h_L,...,h_R. Возьмем, например, в качестве исходной пирамиду h₁,...,h₇ 
                                                               h₁ 
  

                     42                                                                    06 
  

         55                      94                                       18                          12 

и добавим к ней слева элемент h₁=44. Новая пирамида получается так: сначала x ставится наверх древовидной структуры, а затем он постепенно опускается вниз каждый раз по направлению наименьшего из двух примыкающих к нему элементов, а сам этот элемент передвигается вверх. В приведенном примере значение 44 сначала меняется местами с 06, затем с 12 и в результате образуется дерево 

                                                               06 
 
                      42                                                                        12 

  
       55                      94                                               18                           44 

Р.Флойдом был предложен способ построения пирамиды ╚на том же месте╩. Его процедура сдвига представлена в программе процедурой sift. 
Процесс формирования пирамиды из n элементов h₁,...,h_n на том же месте описывается так: 

L:=(n div 2) +1; 
while L>1 DO begin L:=L-1; sift(L,n); end; 

type mass=array[1..100] of integer; 
var   k,i,j,x: integer; 
        a: mass; 
  procedure sift ( var a: mass; l,r: integer); 
    begin 
      i:=l;j:=2*l;x:=a[l]; 
          if (j<r) and (a[j]<a[j+1]) then j:=j+1; 
          while (j<=r) and (x<a[j]) do 
              begin 
                  x:=a[i]; a[i]:=a[j]; a[j]:=x; 
                  i:=j; j:=2*j; 
                  if (j<r) and (a[j]<a[j+1]) then j:=j+1; 
              end; 
     end; 
  procedure Heapsort (var a: mass; n: integer); 
      var  l,r: integer; 
          begin 
               l:=(n div 2)+1; r:=n; 
               while l>1 do 
                    begin 
                        l:=l-1; 
                        sift(a,l,r); 
                    end; 
               while r>1 do 
                    begin 
                         x:=a[1]; a[1]:=a[r]; a[r]:=x; r:=r-1; 
                         sift(a,l,r); 
                    end; 
          end; 
  Begin  randomize; 
     readln(k); 
     for i:=1 to k do 
          begin 
               a[i]:=random(100);write(a[i],'  '); 
          end; writeln; 
      heapsort(a,k); 
      writeln; 
      for i:=1 to k do 
      write(a[i],'  '); 
      writeln; 
  End. 

На первый взгляд вовсе не очевидно, что такой метод сортировки дает хорошие результаты. Ведь в конце концов большие элементы, прежде чем попадут на свое место в правой части, сначала сдвигаются влево. Процедуру не рекомендуется применять для небольшого, вроде нашего примера, числа элементов. Для больших же n Heapsort очень эффективна; чем больше n, тем лучше она работает. 

В худшем случае нужно n/2 сдвигающих шагов, они сдвигают элементы на log₂(n/2), log₂(n/2-1),...,log₂(n-1) позиций (логарифм ╚обрубается╩ до следующего меньшего целого). Следовательно, фаза сортировки требует   n-1 сдвигов с самое большое log₂(n-1), log₂(n-2),...,1 перемещениями. Кроме того, нужно еще n-1 перемещений для просачивания сдвинутого элемента на некоторое расстояние вправо. Эти соображения показывают, что даже в самом плохом из возможных случаев Heapsort потребует n*log₂n шагов. 
 

Теперь коснемся третьего улучшенного метода, основанного на обмене. Улучшение метода, основанного на обмене, оказывается, приводит к самому лучшему из известных в данный момент методу сортировки для массивов. Изобретатель Ч.Хоар назвал этот метод быстрой сортировкой (Quicksort). 

В Quicksort исходят из того соображения, что для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. 

Давайте, попытаемся воспользоваться таким алгоритмом: выберем наугад какой-либо элемент (назовем его x) и будем просматривать слева наш массив до тех пор, пока не обнаружим элемент a_i>x, затем будем просматривать массив справа, пока не встретим a_j<x. Теперь поменяем местами эти два элемента и продолжим наш процесс просмотра и обмена, пока оба просмотра не встретятся где-то в середине массива. В результате массив окажется разбитым на левую часть, с ключами меньше (или равными) x, и правую с ключами больше (или равными) x. Если взять в качестве x для сравнения средний ключ 42, то в массиве ключей 

44  55  12  42  94  06  18  67 

     18  06  12  42  94  55  44  67 

Наша цель - не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям частей, и так до тех пор пока каждая из частей не будет состоять из одного-единственного элемента. 

Суть итеративного решения заключается во введении списка требуемых разделений, т.е. разделений, которые необходимо провести. На каждом этапе возникают две задачи по разделению. И только к одной из них мы можем непосредственно сразу приступить в очередной итерации, другая же заносится в упомянутый список. При этом, конечно, существенно, что требования из списка выполняются несколько специфическим образом, а именно в обратном порядке. Следовательно, первое из перечисленных требований выполняется последним, и наоборот. В приводимой не рекурсивной версии Quicksort каждое требование задается просто левым и правым индексами - это границы части, требующей дальнейшего разделения. Вводим индекс s, указывающий на самую последнюю строку в стеке. О том, как выбрать подходящий размер стека m, речь пойдет при анализе Quicksort. 

const m=4; n=20; 
type stack=record 
     t,r:integer; 
     end; 
type mass=array[1..n] of integer; 
var i,j,t,r,x,w:integer; 
    s: 0..m; 
    a: mass; 
    st: array[1..m] of stack; 

Begin 
   for i:=1 to n do 
     begin 
       a[i]:=random(100); write(a[i],'  '); 
     end; 
   s:=1; st[s].t:=1; st[s].r:=n; 
   repeat  {выбор из стека последнего запроса} 
     t:=st[s].t;r:=st[s].r;s:=s-1; 
       repeat  {разделение a[t]...a[r]} 
         i:=t;j:=r;x:=a[(l+r) div 2]; 
         repeat 
           while a[i]<x do i:=i+1; 
           while x<a[j] do j:=j-1; 
           if i<=j then 
                   begin  w:=a[i];a[i]:=a[j];a[j]:=w; 
                          i:=i+1;j:=j-1; end; 
         until i>j; 
         if i<r then   {запись в стек запроса из правой части} 
                begin s:=s+1; st[s].t:=i;st[s].r:=r; end; 
         r:=j;  {теперь t и r ограничивают левую часть} 
       until t>=r; 
   until s=0; 

   writeln; 
   for i:=1 to n do 
     write(a[i],'  '); 
End. 

m = [Sx:1 <= x <= n:(x-1)*(n-(x-1))/n]/n 
    = [Su: 1<= x <= n-1:u*(n-u)]/n² 
    = [n*(n-1)/2n-(2n²-3n+1)/6n = (n-1/n)/6 

Литература 

1.  Н.Вирт. Алгоритмы и структуры данных. 
2.  Д.Кнут. Искусство программирования для ЭВМ. 

1.  Дан массив целых чисел a[1..n]. Отсортировать его методом Шелла. 
2.  Найти количество различных чисел среди элементов данного массива. Число действий порядка nlogn. (В решение использовать изученные сортировки). 
3.  Найти перестановку элементов 1, 2,  3, ..., n, при которой быстрая сортировка ведет себя наихудшим (наилучшим) образом (n=5, 6, 7).