algorithm - 流数据的归并排序算法

Question

我正在阅读以下链接中的合并排序

http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx

Merge sort's claim to fame is that it can easily be modified to handle sequential data such as from a stream or a generator. Another huge benefit is that when written carefully, merge sort does not require that all items be present. It can sort an unknown number of items coming in from a stream or generator, which is a very useful property.

我的问题是

1.我的理解是合并排序需要完整数组，因为我们必须在数组之间划分数组并独立排序，然后合并。如果不是所有项目都存在，合并排序算法如何工作？

1. 用简单的术语给出一个算法如何将合并排序算法用于来自流的项目？

Answer 1

1 和 2 的答案有些相关。

1. 您仍然可以对不完整的数组执行mergesort，这会留下一个已排序的、部分完整的数组。运行时间仍然是 O(n lg n)。至于插入剩余的项目，您可以将部分数组与新项目合并，或者一次插入一个新项目，q.v。下面的第 2 部分。如果原始数组接近完成，则一次插入一个剩余项的效果最好。

2. 假设您从一个排序的数字数组开始，当新数字一个一个地从流中传入时，您将不必运行另一个 mergesort。相反，您可以简单地在 O(n) 时间内遍历排序数组并插入来自流的每个新项目。