就地合并，无需外部存储

Question

我想将两个具有排序值的数组合并为一个。由于两个源数组都存储为大型数组的后续部分，我想知道您是否知道如何将它们合并到大型存储中。意思是就地合并。

我发现的所有方法都需要一些外部存储。它们通常需要 sqrt(n) 临时数组。没有它有没有有效的方法？

我正在使用 C#。也欢迎其他语言。提前致谢！

Answer 1

AFAIK，如果不显着增加必要的比较和元素移动次数，合并两个（甚至已排序）数组就无法就地工作。请参阅：合并排序。然而，存在阻塞变体，它们能够通过利用长度 sqrt(n) 的临时数组对长度为 n 的列表进行排序 - 正如您所写 - 通过仍然保持操作数量相当低。它不错 - 但它也不是“什么都没有”，显然是你能得到的最好的。

对于实际情况，如果您负担得起，您最好使用临时数组来合并列表。

Answer 2

如果这些值存储为较大数组的连续部分，您只需对数组进行排序，然后删除相等的连续值。

void  SortAndDedupe(Array<T> a)
{
    // Do an efficient in-place sort
    a.Sort();
    // Now deduplicate
    int lwm = 0; // low water mark
    int hwm = 1; // High water mark
    while(hwm < a.length)
    {
        // If the lwm and hwm elements are the same, it is a duplicate entry.
        if(a[lwm] == a[hwm])
        {
            hwm++;
        }else{
            // Not a duplicate entry - move the lwm up
            // and copy down the hwm element over the gap.
            lwm++;
            if(lwm < hwm){
                a[lwm] = a[hwm];
            }
            hwm++;
        }
    }
    // New length is lwm
    // number of elements removed is (hwm-lwm-1)
}

在您认为这太慢之前，请实施它并对其进行分析。这应该需要大约十分钟。

编辑：这当然可以通过使用不同的排序而不是内置排序来改进，例如快速排序、堆排序或平滑排序，具体取决于哪种排序在实践中提供更好的性能。请注意，硬件架构问题意味着实际性能比较可能与大 O 分析的结果有很大不同。

实际上，您需要在实际硬件/操作系统平台上使用不同的排序算法对其进行分析。

注意：我并不是试图在这个答案中给出一个学术答案，我试图给出一个实用的答案，假设你正在尝试解决一个真正的问题。

Answer 3

不关心外部存储。 sqrt(n) 或更大的值不会损害您的性能。您只需确保存储是池化的。特别是对于大数据。特别是对于将它们合并到循环中。否则，GC 将会承受压力并消耗相当一部分 CPU 时间/内存带宽。