Требования к итератору быстрой сортировки

tl; dr: Можно ли эффективно реализовать быструю сортировку в двусвязном списке? До того, как я подумал об этом, я понял, что нет, это не так.

На днях у меня была возможность рассмотреть требования к итератору для основных алгоритмов сортировки. Базовые O (N²) довольно просты.

• Пузырьковая сортировка - два итератора вперед подойдут, перетаскивая один за другим.
• Сортировка вставкой - подойдут 2 двунаправленных итератора. Один для неупорядоченного элемента, один для точки вставки.
• Сортировка выделения - немного сложнее, но итераторы вперед могут помочь.

Quicksort

Для introsort_loop в std :: sort (как в стандартной библиотеке GNU / hp (1994) / Silicone graphics (1996)) требуется, чтобы он был random_access.

__introsort_loop(_RandomAccessIterator __first,
         _RandomAccessIterator __last,
         _Size __depth_limit, _Compare __comp)

Как я и ожидал.

Теперь, при ближайшем рассмотрении, я не могу найти настоящую причину, чтобы требовать это для быстрой сортировки. Единственное, что явно требует random_access_iterators, - это вызов std :: __ median , который требует вычисления среднего элемента. Обычная быстрая сортировка не вычисляет медианное значение.

Разделение состоит из проверки

 if (!(__first < __last))
    return __first;

Не очень полезная проверка для двунаправленных адресов.Однако следует иметь возможность заменить это проверкой в ​​предыдущем перемещении по разделам (слева направо / справа налево) с простым условием

if ( __first == __last ) this_partitioning_is_done = true;

Можно ли реализовать быструю сортировку достаточно эффективно, используя только двунаправленные итераторы? Рекурсивную глубину все еще можно охранять.

NB. Я еще не пытался реализовать его.