Битонная сортировка

Алгоритм основан на понятии битонных последовательностей и операций над ними.
 

Чтобы превратить любую битонную последовательность в отсортированную, нужно:

  1. Разделить последовательность пополам, попарно сравнить элементы xi и xn/2+i, меняя их местами, если элемент из первой половины больше(или меньше).
  2. Рекурсивно выполнить эту сортировку над каждой из получившихся половин.

 

Чтобы превратить произвольную последовательность в битонную, нужно:

  1. Разделить последовательность пополам.
  2. Первую часть превратить в битонную последовательность и отсортировать по возрастанию.
  3. Вторую часть превратить в битонную и отсортировать по убыванию. 

 Последовательность из двух элементов - битонная по определению.

type
  TAI = array of integer;
...
procedure BitonicSort(var A: TAI);
var
    N: integer; // длина рабочего массива
    W: TAI;
    i: Integer;

    // Битонная сортировка
    procedure SortBS(Left, Right: integer; Asc: boolean);
    var
        mid: integer;
        i,j : integer;
    begin
      // Последовательность из одного элемента сортировать не нужно.
      if Right-Left < 1 then Exit;
      // Находим середину.
      mid := (Left + Right) div 2 +1;
      // Элементы каждой половины сравниваем и обмениваем попарно.
      i := Left;
      j := mid;
      while (i<mid) and (j<=Right) do
      begin
        if Asc xor (W[i]<W[j]) then swap(W[i], W[j]);
        inc(i);
        inc(j);
      end;
      // Выполняем сортировки для каждой из получившихся половинок.
      SortBS(Left, mid-1, Asc);
      SortBS(mid, Right, Asc);
    end;

    // Превращаем диапазон в битонную последовательность
    procedure MakeBS(Left, Right: integer);
    var
        mid: integer;
    begin
      // Один или два элемента - уже битоновая последовательность.
      if Right-Left <= 1 then Exit;
      // Находим середину.
      mid := (Left + Right) div 2 +1;
      // Левую половину превращаем в битонную,
      MakeBS(Left, mid -1);
      // а затем в отсортированную по возрастанию.
      SortBS(Left, mid -1, True);
      // Правую половину превращаем в битонную,
      MakeBS(mid, Right);
      // а затем в отсортированную по убыванию.
      SortBS(mid, Right, False);
      // Теперь весь диапазон W[Left..Right] - битонная последовательнось
    end;

begin
  // Наращиваем массив до степени двойки
  N := 1;
  while N < Length(A) do
    N := N shl 1;
  SetLength(W, N);
  for i := Low(A) to High(A) do
    W[i] := A[i];
  for i := High(A)+1 to High(W) do
    W[i] := MaxInt;
  // Превращаем последовательность в битонную.
  MakeBS(Low(W), High(W));
  // превращаем битонную последовательность в отсортированную.
  SortBS(Low(W), High(W), True);
  // Забираем результат.
  for i := Low(A) to High(A) do
    A[i] := W[i];
end;

Сложность:

Максимальная O(N log2N)
Минимальная O(N log2N)
Средняя O(N log2N)

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