“就地”迭代LSD n基排序

Question

是否有可能实现“就地”迭代LSD n基排序？澄清:我已经阅读了维基百科在原位MSD基排序.上面写着：

计数排序用于确定每个回收站的大小及其起始索引。

因此，需要一个辅助数组来存储索引，但是如果这是它所需要的，我仍然认为它是一个就地算法(因为这个数组的大小仅为n-基排序)。我还读过这个答案，其中再次实现了递归MSD基排序。它也没有n-基排序的通用实现。

Answer 1

编辑:我终于在答案：https://cs.stackexchange.com/questions/93563/fast-stable-almost-in-place-radix-and-merge-sorts中描述了我的算法

是。实际上，将输入数据分割成一定大小的页面(4KB将很好)。然后在您使用这些页面的数据时重用它们。您将需要一些额外的内存，但对于初始桶最多需要n页，下一页指针(每页一个指针)，头_page/current_page/current_ will _ptr每个桶的3*n个指针。

阿尔戈：

1. 将它们放入空闲页面列表中。
2. 处理输入数据，将条目移动到它们的桶中。处理完整个输入数据页后，将此页添加到空闲页列表中。填充完整个桶页后，将其添加到此桶页的列表中，并从空闲列表中分配新的。您将得到每个bicket的页面列表，此列表中的最后一页已部分填充
3. 按桶的顺序将数据移动到原来的数组中。

当然，如果您需要多个LSD传递，您可以跳过步骤3，除了最后一次传递，并且直接从步骤2生成的列表开始每个排序传递。