c++ - 在 C++ 中，为什么要求列表在合并之前必须排序

Question

在C++中，列表数据结构有一个合并功能，基本上删除源列表中的所有对象并放入目标列表。

// source list will be empty after this operation
destinationList.merge(sourceList);

根据教程/示例，在合并操作之前必须对列表进行排序。

destinationList.sort();
sourceList.sort();
destinationList.merge(sourceList);

我很困惑，因为如果需要对列表进行排序，为什么 C++ 不通过在合并函数中调用排序函数来强制执行它？

另外，我可以先合并未排序的列表，然后我可以对合并后的列表进行排序，这不是一样吗？

destinationList.merge(sourceList);
destinationList.sort();

Answer 1

why there is a requirement that lists must be sorted before merging?

merge 的目的是合并两个排序列表以创建一个新的排序列表，而无需执行另一次排序的开销。合并可以在线性时间内完成，而排序是 O(n*log(n))。

why c++ doesn't enforce it by calling sort function in the merge function ?

因为，如果列表已经排序，那将是非常低效的。

Another thing, i can first merge unsorted lists, then i can sort merged list, isn't this same ?

没有。合并算法要求对输入进行排序，并从中生成一个排序列表。它的工作原理是比较输入列表的第一个元素，取较低的元素，并将其附加到输出列表。

您可以通过附加两个列表然后对结果进行排序来实现相同的目的；但同样，如果列表已经排序，那将是低效的。