c++ - 二元归并排序和自然归并排序

Question

我知道家庭作业问题在这里不是最受欢迎的，但我完全不知所措。我正在做一项作业，要求我们制定多种排序算法。然而，其中一个让我发疯。我在网上找不到任何例子，而且他在类里面也没有完全复习过。我们必须进行如下所示的合并排序:

void mergeSort(int * a, int s, bool n = false)

其中 a 是数组，s 是所述数组的大小，n 对于二进制归并排序为 false，对于自然归并排序为 true。问题是，我找不到什么是自然归并排序和二元归并排序。我只是找到合并排序。他们都要求更多的变量。

我只是问是否有人知道在哪里可以找到对这两种不同类型的合并排序的很好的解释。

Answer 1

我不是该主题的专家，但维基百科页面似乎是一个很好的起点 http://en.wikipedia.org/wiki/Merge_sort

它包含一个关于自然归并排序的部分和一个例子。

关于二元归并排序:

A variant named binary merge sort uses a binary insertion sort to sort groups of 32 elements, followed by a final sort using merge sort. It combines the speed of insertion sort on small data sets with the speed of merge sort on large data sets

插入排序可以在这里阅读:http://en.wikipedia.org/wiki/Insertion_sort

其中包含有关二进制插入排序的选择。

关于变量。 “自下而上归并排序”(其中自然归并排序是一个变体)的维基百科示例具有以下签名:

void BottomUpSort(A[], B[], n)

其中 A 是要排序的数组，n 是它的长度。 B 是一个工作数组，如果 a 正确阅读算法，它的长度也需要为 n。无论如何，它可以在算法的开头创建并在最后删除。