如何在K-Way Partitioning算法中填充枢轴边界数组q？

我已实现基于Peter Taylor方案的K-Way Partitioning快速排序，现需在分区过程中填充给定的q数组，使其记录每个枢轴对应的区间边界（即小于枢轴和等于枢轴的值的区间边界）。

现有实现代码 #

#pragma once
template <class T>
class KWayPartition {
private:
    void swap(T* a, T* b) { T temp = *a; *a = *b; *b = temp; }
    int partition(T* A, int low, int high, T* lp,int* q)
    {
        if (A[low] > A[high]){
            swap(&A[low], &A[high]);
        }
        int j = low + 1;
        int g = high - 1, k = low + 1;
        T p = A[low], qq = A[high];
        while (k <= g) {
            if (A[k] < p) {
                swap(&A[k], &A[j]);
                j++;
            }
            else if (A[k] >= qq) {
                while (A[g] > qq && k < g){
                    g--;
                }
                swap(&A[k], &A[g]);
                g--;
                if (A[k] < p) {
                    swap(&A[k], &A[j]);
                    j++;
                }
            }
            k++;
        }
        j--;
        g++;
        swap(&A[low], &A[j]);
        swap(&A[high], &A[g]);
        *lp = j;
        return g;
    }
    void insertionSort(T A[], T r) {
        T ki;
        int j=0;
        for (int i=1;i<r;i++) {
            ki = A[i];
            j = i - 1;
            while (j >= 0 && A[j] > ki) {
                A[j+1] = A[j];
                j--;
            }
            A[j+1] = ki;
        }
    }
    void KPartition (T* A, T* pivots,int *q, int p, int r, int sp, int sr) {
        if (r<=p) {
            return;
        }
        if (sp<sr) {
            insertionSort(A,r);
        }
        else {
            int mid = p+(r-p)/2;
            int idx = partition(A, p, r, &pivots[mid],q);
            KPartition(A, pivots,q,p, idx - 1,r,mid - 1);
            KPartition(A, pivots,q,idx + 1, r ,mid+1,sr);
        }
    }
public:
    virtual void Partition (T* A, T* pivots, int* q, int p, int r, int k) {
        KPartition(A, pivots,q, p,r+1, 0,0);
    }
};

注意事项 #

• 枢轴数组pivots已给定，实现过程中禁止使用标准库函数。

逻辑参考 #

我认为其逻辑类似Python中的sorted函数（非原地排序），对应的键函数如下：

[](T* a, T* b) {
    for (auto i : pivots) if (a[i] != b[i]) return a[i] < b[i];
    return false;
}

最终需满足的分区属性 #

A[p .. r]
pivots[0 .. (k-1)]  升序排列的k个值组成的数组
q[0 .. (2k-1)]      输出的边界数组
最终需满足：
    A[p .. q[0]-1] < pivots[0]
    A[q[0] .. q[1]-1] = pivots[0]
    pivots[0] < A[q[1] .. q[2]-1] < pivots[1]
    A[q[2] .. q[3]-1] = pivots[1]
    ...
    pivots[i-1] < A[q[2i-1] .. q[2i]-1] < pivots[i] （0 < i < k-1）
    A[q[2i] .. q[2i+1]-1] = pivots[i]       （0 < i < k-1）
    ...
    pivots[k-2] < A[q[2k-3] .. q[2k-2]-1] < pivots[k-1]
    A[q[2k-2] .. q[2k-1]-1] = pivots[k-1]
    A[q[2k-1] .. r] > pivots[k-1]

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