迭代合并排序，工作速度与冒泡排序相同

Question

我尝试使用嵌套循环实现迭代合并排序。虽然这个算法确实排序正确（就像排序后的顺序正确一样），但我知道这个实现有问题，因为我试图用它对较大的集合进行排序并将时间与较慢的排序进行比较，但我最终得到了缓慢的时间对于这个迭代实现。例如，对 500 个项目进行排序需要 31 毫秒的时间，就像冒泡排序一样。

  int main()
  {

      int size;
      cin >>  size;
      //assume vector is already initialized with values & size
      vector<int> items(size);
      IterativeMergeSort(items, 0, size - 1);
  }
  void IterativeMergeSort(vector<int> &items, int start, int end)
  {
    vector<int> temp(items.size());
    int left, middle, right;
    for(int outer = 1; outer < 2; outer *= 2)
    {
    for(int inner = start; inner < end; inner = inner * outer + 1)
    {
        left = outer - 1;
        middle = inner;
        right = inner + 1;
        ItMerge(items, left, middle, right, temp);
    }
   }
 }
  void ItMerge(vector<int> &items, int start, int mid, int end, vector<int> &temp)
{
int first1 = start;
int last1 = mid;
int first2 = mid + 1;
int last2 = end;

int index = first1;
while(first1 <= last1 && first2 <= last2)
{
    if(items[first1] <= items[first2])
    {
        temp[index] = items[first1];
        first1++;
    }
    else
    {
        temp[index] = items[first2];
        first2++;
    }
    index++;
}
while(first1 <= last1)
{
    temp[index] = items[first1];
    first1++;
    index++;
}
while(first2 <= last2)
{
    temp[index] = items[first2];
    first2++;
    index++;
}
for(index = start; index <= end; index++)
{
    items[index] = temp[index];
}
}

Answer 1

下面是一个 link 自上而下和自下而上合并排序的优化示例。自下而上的合并排序要快一点，因为它跳过了用于重复生成索引子对直到一个子对表示大小为 1 的运行的递归序列。大部分时间都花在合并上，所以 bottom起来并没有那么快。自下而上合并过程的第一遍可以通过就地交换对而不是复制它们来优化。自下而上的合并排序以临时数组或原始数组中的排序数据结束。如果需要原始数组，则可以计算通过计数，如果计数为奇数，则第一遍交换到位。

在我的系统（Intel Core i7 2600k 3.4ghz）上，这两个版本都可以在不到一秒的时间内对 400 万个 64 位无符号整数进行排序。

对于向量或整数数组，计数/基数排序会更快。

Answer 2

您的算法不是归并排序。它试图成为，但它不是。

据我了解，应该发生的是内循环跨过子序列并合并它们，而外循环控制内循环的序列长度，从 1 开始并在每次迭代时加倍，直到只有两个子序列，它们被合并。

但这不是您的算法正在做的事情。外循环的条件被打破，所以外循环将运行恰好一次。并且内部循环不会成对采用大致相等的子序列。相反，右边的子序列恰好是一个元素（mid 是 inner，right 是 inner+1），左边的子序列总是到目前为止使用的所有元素（left是 outer-1，而 outer 是常量 1)。因此该算法将重复将已排序的左子序列与单元素右子序列合并。

这意味着实际上，你的算法是插入排序，只不过你不是原地插入，而是将排序后的序列复制到缓冲区，在适当的时候插入新元素，然后复制结果背部。所以这是一个非常低效的插入排序。

Answer 3

我终于想通了。

在伪代码中：

  for( outer = 1, outer < length, outer *=2)
     for(inner = 0; inner < length, inner = inner + (outer *2))
        left = inner
        middle = (inner + outer) - 1
        right = (inner + (outer * 2)) - 1
        merge(items, left, middle, right, temp)

在重新思考迭代合并排序应该如何工作并查看几个实现之后，在合并方法中，我需要做的就是检查传入的中间和右侧索引是否大于或等于向量大小（这样我们处理任何可能超出范围的值），然后像往常一样合并。另外，查看 this helped greatly understand it; also this。只是为了确保它与递归合并排序一样有效，我对两个（递归和迭代）实现都进行了计时，为 500、1000、5000 和 10K 值排序产生了相同的时间（在某些情况下，迭代解决方案产生了更快的时间）。

迭代合并排序，工作速度与冒泡排序相同

Iterative Merge Sort, works same speed as Bubblesort

c++

sorting

iteration

mergesort