Eldar Musayev

Вчера супруга, которая решила посмотреть вокруг место работы получше и начала каждый вечер делать программистские задачки на C#, C++ и Python, полвечера убила на быструю сортировку (quicksort). Я тем временем опять удивился насколько много граничных условий вылезает в исходном алгоритме Хоара. Да-да, знаю, уже придумали улучшенную и починенную версию, но захотелось исправить сохранив дух решения, с двумя индексами сходящимися к центру. И вот что получилось. Вроде работает. Кто-нибудь видит баг?

static public void Quicksort(int[] ar)
{
     if (ar.Length > 1) Quicksort(ar, 0, ar.Length - 1);
}

static private void Quicksort(int[] ar, int left, int right)
{
     if (left == right) return;
     int i = left + 1;
     int j = right;
     int pivot = ar[left];

     // Loop invariant i <= j
     while (i < j)
     {
          if (ar[i] <= pivot) i++;
          else if (ar[j] > pivot) j--;
          else
          { // Swap ith and jth elements
               int m = ar[i]; ar[i] = ar[j]; ar[j] = m;
          }
     }
     // Now i == j

     if (ar[j] <= pivot /* it also means that i == right, because j was never moved */)
     {
          // Left most element is array's maximum
          int m = ar[left]; ar[left] = ar[right]; ar[right] = m;
          Quicksort(ar, left, right-1);
     }
     else
     {
          Quicksort(ar, left, i - 1);
          Quicksort(ar, i, right);
     }
}

Пока возился обратил внимание на забавный момент: как бы ни распределялись данные, количество нетривиальных вызовов Quicksort (когда i<j) всегда равно длине массива минус один. Сначала удивился, а потом дошло почему. Можете ответить? Ответ вот здесь (да, да, я решил перестать публиковать белым по белому. Слишком много браузеров на которых это не работает).