使用 C 合并 k 个排序数组

Question

我需要将 k (1 <= k <= 16) 个排序数组合并为一个排序数组。这是一个家庭作业，教授要求使用 O(n) 算法来完成。合并 2 个数组没有问题，我可以使用 O(n) 算法轻松完成。我觉得我的教授所要求的对于使用 O(n) 算法的 n 个数组是可撤销的。

我使用下面的算法来拆分数组索引并在每个分区上运行 InsertionSort。我可以将这些开始和结束索引保存到一个二维数组中。我只是不知道如何使用 O(n) 完成合并，因为这将需要多个循环。如果可能的话，有没有人有任何提示。我不是在寻找实际的代码，只是一个关于我应该从哪里开始的提示/

int chunkSize = round(float(arraySize) / numThreads);
for (int i = 0; i < numThreads; i++) {
    int start = i * chunkSize;
    int end = start + chunkSize - 1;
    if (i == numThreads - 1) {
        end = arraySize - 1;
    }

    InsertionSort(&array[start], end - start + 1);
}

编辑：要求是算法是 O(n)，其中 n 是数组中的元素数。另外，我需要在不使用最小堆的情况下解决这个问题。

编辑#2：这是我想出的算法。这里的问题是我没有将每次迭代的结果存储回原始数组。我可以将所有内容复制回循环中，但这会很昂贵。除了使用某些东西之外，我还有什么办法可以做到这一点memcpy吗？在下面的代码中，indices是一个二维数组 [numThreads][2]，其中 array[i][0] 是第 i 个数组的开始索引，array[i][1] 是结束索引。

void mergeArrays(int array[], int indices[][2], int threads, int result[]) {
    for (int i = 0; i < threads - 1; i++) {
        int resPos = 0;
        int lhsPos = 0;
        int lhsEnd = indices[i][1];
        int rhsPos = indices[i+1][0];
        int rhsEnd = indices[i+1][1];

        while (lhsPos <= lhsEnd && rhsPos <= rhsEnd) {
            if (array[lhsPos] <= array[rhsPos]) {
                result[resPos] = array[lhsPos];
                lhsPos++;
            } else {
                result[resPos] = array[rhsPos];
                rhsPos++;
            }
            resPos++;
        }

        while (lhsPos <= lhsEnd) {
            result[resPos] = array[lhsPos];
            lhsPos++;
            resPos++;
        }

        while (rhsPos <= rhsEnd) {
            result[resPos] = array[rhsPos];
            rhsPos++;
            resPos++;
        }
    }
}

Answer 1

您可以使用算法将K 个排序数组合并为一个排序数组O(N*log(K))，使用具有 K 个条目的优先级队列，其中N是所有数组中元素的总数。

如果K被视为常数值（在您的情况下受 16 的限制），则复杂度为O(N).

再次注意：N是我帖子中的元素数，而不是数组数。不可能在 O(K) 中合并数组 - 简单复制需要 O(N)