能否借助缓冲区实现完全原地迭代快排？及递归O(logn)转O(1)探讨

注：允许使用大小固定、不随列表规模变化的辅助数组。未优化的Quicksort（快速排序）和Mergesort（归并排序）均为递归算法，占用O(logn)栈空间（归并排序合并步骤的O(n)空间不计入）。

在研究Block Merge sorts（块归并排序）的各类变体（包括原始论文版本、简化版Sqrtsort、Wikisort、Grailsort、Holy Grailsort）后，我尝试寻找原地稳定快速排序，发现了aphitorite开发的Logsort算法。

Logsort的核心特性（来自项目说明） #

众所周知，Quicksort是一种O(n log n)复杂度的算法，通过O(n)复杂度的分区操作实现排序。这类分区操作可轻松实现原地执行（占用O(1)额外空间），但不具备稳定性，即无法保留相等元素的原有顺序。稳定Quicksort也可达到O(n log n)时间复杂度，但需额外O(n)空间实现稳定分区，不再属于原地算法。
Logsort是一款新颖实用的O(n log n)复杂度快速排序算法，兼具原地性与稳定性。该算法通过O(log n)空间实现O(n)时间复杂度的稳定分区，因此得名；尽管未达到最优O(1)空间，仍被多数人视为原地算法。与std::stable_sort这类O(n log² n)复杂度的知名原地稳定排序算法不同，Logsort具有渐近最优性。

待探讨的疑问 #

• Logsort的栈空间占用极小，实际影响可忽略不计（例如2^40约等于1万亿），但能否借助缓冲区将任何因递归占用O(logn)内存的算法转换为占用O(1)内存的版本？
• 能否利用缓冲区实现完全原地的迭代式快速排序？

内容的提问来源于stack exchange，提问作者Lamphiq