实施，而无需使用额外的阵列一个合并？ [英] Implementing a mergesort without using an additional array?

问题描述

我最近读了很多关于归并，我不知道是否有办法做一个合并，而无需使用至少一个附加阵列。这可能吗？

I've read a lot about mergesort recently and I wonder if there is a way to do a mergesort without using at least one additional array. Is it possible?

推荐答案

根据维基百科该的确是可能的，但可能不会产生任何性能增益：

According to Wikipedia it is indeed possible, but might not yield any performance gain:

排序就地是可能的（例如，使用列表而不是数组），但非常复杂，并会提供在实践中很少的性能提升，即使该算法为O（ N 的日志 N 的）时间。在这些情况下，像堆排序算法通常提供可比较的速度，和远不如复杂。另外，与标准归并排序，就地合并排序是没有一个稳定的排序。在链表的情况下的算法不使用更多的空间比该已使用的列表重新presentation，但O（日志（的 K 的）），用于递归跟踪。有人会说，排序链表不到位，因为即使你是在给定的数据结构进行排序，数据结构本身具有O（ N 的），你操纵（额外的数据，例如，链接在列表中）。

Sorting in-place is possible (e.g., using lists rather than arrays) but is very complicated, and will offer little performance gains in practice, even if the algorithm runs in O(n log n) time. In these cases, algorithms like heapsort usually offer comparable speed, and are far less complex. Additionally, unlike the standard merge sort, in-place merge sort is not a stable sort. In the case of linked lists the algorithm does not use more space than that the already used by the list representation, but the O(log(k)) used for the recursion trace. Some would argue that sorting a linked list is not in place because even though you are sorting in the given data structure, the data structure inherently has O(n) extra data you are manipulating (e.g., the links in the list).

这篇关于实施，而无需使用额外的阵列一个合并？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！