arrays - 为什么合并排序对大数组更好，而快速排序对小数组更好？

Question

我看到使用合并排序而不是快速排序的唯一原因是列表是否已经(或大部分)排序。

归并排序需要更多空间，因为它会创建一个额外的数组用于存储，并且无论如何它都会比较每个项目。

另一方面，快速排序不需要额外的空间，也不会进行不必要的交换或比较。

因为大数据集或小数据集而说一个比另一个好似乎不符合直觉。

例如，引用 Geeksforgeeks 上的文章:

Merge sort can work well on any type of data sets irrespective of its size (either large or small).whereasThe quick sort cannot work well with large datasets.

接下来它说:

Merge sort is not in place because it requires additional memory space to store the auxiliary arrays.whereasThe quick sort is in place as it doesn’t require any additional storage.

我知道空间复杂度和时间复杂度是不同的。但这仍然是一个额外的步骤，当然，将所有内容写入具有大数据集的新数组将花费更多时间。

至于旋转问题，数据集越大，选择最低或最高项目的机会就越低(除非，同样，它是一个几乎排序的列表)。

那么为什么认为归并排序比快速排序更适合对大型数据集进行排序？

Answer 1

Why is Merge sort better for large arrays and Quick sort for small ones?It would seem unintuitive to say that because of large or small data sets one is better than the other.

假设数据集适合内存(未调出)，问题不在于数据集的大小，而是导致 O(n^{2) 时间复杂度。快速排序可以使用中位数的中位数来保证最坏情况下的时间复杂度为 O(n log(n))，但这最终会使它比合并排序慢得多。如果递归级别变得太深，另一种方法是切换到堆排序，称为介绍排序，并在某些库中使用。}

https://en.wikipedia.org/wiki/Median_of_medians

https://en.wikipedia.org/wiki/Introsort

Merge sort requires more space as it creates an extra array for storing, and no matter what it will compare every item.

合并排序的变体不需要任何额外的数据存储，但它们往往比标准合并排序慢 50% 以上。

Quick sort on the other hand does not require extra space, and doesn't swap or compare more than necessary.

子数组的每个元素都将与枢轴元素进行比较。随着相等元素个数的增加，Lomuto 分区方案变得更差，而 Hoare 分区方案变得更好。对于大量相等的元素，Hoare 分区方案不必要地交换相等的元素，但避免交换的检查通常比仅仅交换花费更多的时间。

sorting an array of pointers to objects

与快速排序相比，归并排序执行更多的移动但更少的比较。如果对指向对象的指针数组进行排序，则只会移动指针，但比较对象需要遵守指针以及比较对象所需的内容。在这种情况下以及比较比移动花费更多时间的其他情况下，归并排序更快。

large datasets that don't fit in memory

对于太大而无法放入内存的数据集，基于内存的排序用于对适合内存的数据集“ block ”进行排序，然后写入外部存储。然后使用 k-way 合并将外部存储上的“ block ”合并以生成排序的数据集。

https://en.wikipedia.org/wiki/External_sorting