Итеративная реализация быстрой сортировки с использованием стека пар и пространства памяти

Question

Ниже приведен код, который мне трудно понять, в основном это итеративная реализация Quicksort, использующая явный стек, и я должен сделать 3 вещи.

1: Найти пример, в котором количество пар, хранящихся в стеке, равно Ω (n). 2: найдите способ отредактировать этот код, чтобы сложность памяти была уменьшена до O (log (n)). 3: убедитесь, что после моих правок последний бит, который сортирует остальные элементы, все равно делает это, хотя вероятность каждого элемента одинакова.

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

public void quicksort(int a[ ]) {
  Stack<Pair <Integer ,Integer>>  stack = new Stack<>();
  stack.push(new Pair <Integer ,Integer> (1, a.length − 1));
  int min = 0;

  for(int i = 1; i < a.length; i++) if(a[i] < a[min]) 
    min = i;

  int t = a[0]; a[0] = a[min]; a[min] = t;

  while(!stack.isempty()) {
    Pair <Integer ,Integer>  p = stack.pop();
    int l = p.first(), r = p.second();
    int i = l − 1, j = r , pivot = j;
    do {
      do { i++; } while(a[i] < a[pivot]);
      do { j−−; } while(a[j] > a[pivot]);
      t = a[i]; a[i] = a[j]; a[j] = t;
    } while(i < j);

    a[j] = a[i]; a[i] = a[r ]; a[r ] = t;

    if(r − i > 1) 
      stack.push(new Pair <Integer ,Integer> (i + 1, r ));

    if(i − l > 1) 
      stack.push(new Pair <Integer ,Integer> (l, i − 1));
  }
}

Заранее большое спасибо за помощь, извините за доставленные неудобства!