Случайная сортировка

Самая непрактичная из всех известных... 

Случайно перемешиваем массив, пока не получим отсортированный.

Как-то так:

procedure BogoSort(var A: TAI; out Sorted: boolean);
var
    cnt : integer;

  // Проверка, а не отсортировался ли массив?
  function isSorted: boolean;
  var
    i: Integer;
  begin
    result := true;
    for i := Low(A) to High(A)-1 do
    begin
      if A[i]>A[i+1] then
      begin
        result := false;
        Break;
      end;
    end;
  end;

  // Перемешивание.
  procedure Shuffle;
  var
    i: Integer;
  begin
    for i := Low(A) to High(A) do
     swap(A[i], A[random(Length(A))]);

    inc(cnt);
    Sorted := isSorted;
  end;

begin
  cnt := 0;
  Sorted := false;
  // Пока не отсортировалось, перемешиваем,
  //  Но не более 100000 раз. Чтобы дать возможность
  //  оценить время, необходимое для получения результата.
  while not(Sorted) and (cnt<100000) do
    Shuffle;
end;

Сложность:

Максимальная → ∞
Минимальная O(N)
Средняя O(N * N!)

 

Оценить время можно, например, так:

  ...
  t := TStopWatch.StartNew;
  BogoSort(A, sorted);
  t.Stop;
  if sorted then Answer := Format('Сортировка завершена за %1.3f сек.',[t.ElapsedMilliseconds / 1000]);
            else begin
                   sec := 2;
                   for i := 3 to Length(A) do
                     sec := sec * i;
                   sec := sec / 100000;
                   sec := sec * t.ElapsedMilliseconds / 1000;
                   if sec<120 then Answer := Format('%1.0f сек.',[sec])
                     else
                   begin
                     sec := sec / 60;
                     if sec<90 then Answer := Format('%1.0f мин.',[sec])
                       else
                     begin
                       sec := sec / 60;
                       if sec<72 then Answer := Format('%1.0f ч.',[sec])
                         else
                       begin
                         sec := sec / 24;
                         if sec<365 then Answer := Format('%1.0f дн.',[sec])
                           else
                         begin
                           sec := sec / 365;
                           Answer := Format('%1.1n лет.',[sec]);
                         end;
                       end;
                     end;
                   end;
                   Answer := 'Сортировка остановлена.' + #$0d#$0a +
                             'На вашем компьютере потребуется примерно '+Answer;
                 end;