Изменения

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

Представленная ниже нерекурсивная реализация использует стек, заменяя рекурсивные вызовы помещением в стек параметров функции, а вызовы процедур и выходы из них — циклом, который осуществляет выборку параметров из стека и их обработку, пока стек не пуст. Мы помещаем больший из двух подмассивов в стек первым с тем, чтобы максимальная глубина стека при сортировке <tex>N</tex> элементов не превосходила величины <tex>\log n</tex>.

'''void''' quicksort(a: '''int'''[n], '''int''' l, '''int''' r):

stack <'''int'''> s