c++ - 这是什么类型的归并排序？

Question

这是作业，这是书中提供的排序示例。这是二元归并排序还是自然归并排序？

 #include <iostream>

    #include "util.h"

    /** 
      Merges two adjacent ranges in a vector
     @param a the vector with the elements to merge
    @param from the start of the first range
   @param mid the end of the first range
   @param to the end of the second range
*/
void merge(vector<int>& a, int from, int mid, int to)
{  
   int n = to - from + 1; // Size of the range to be merged 
   // Merge both halves into a temporary vector b 
   vector<int> b(n);

   int i1 = from;
      // Next element to consider in the first half 
   int i2 = mid + 1;
      // Next element to consider in the second half 
   int j = 0; // Next open position in b 

   // As long as neither i1 nor i2 is past the end, move the smaller
   // element into b

   while (i1 <= mid && i2 <= to)
   {  
      if (a[i1] < a[i2])
      {  
         b[j] = a[i1];
         i1++;
      }
      else
      {  
         b[j] = a[i2];
         i2++;
      }
      j++;
   }

   // Note that only one of the two while loops below is executed

   // Copy any remaining entries of the first half
   while (i1 <= mid)
   {  
      b[j] = a[i1];
      i1++;
      j++;
   }
   // Copy any remaining entries of the second half
   while (i2 <= to)
   {  
      b[j] = a[i2];
      i2++;
      j++;
   }

   // Copy back from the temporary vector
   for (j = 0; j < n; j++)
      a[from + j] = b[j];
}

/**  
   Sorts the elements in a range of a vector.
   @param a the vector with the elements to sort
   @param from start of the range to sort
   @param to end of the range to sort
*/
void merge_sort(vector<int>& a, int from, int to)
{  
   if (from == to) return;
   int mid = (from + to) / 2;
   // Sort the first and the second half
   merge_sort(a, from, mid);
   merge_sort(a, mid + 1, to);
   merge(a, from, mid, to);
}

我知道自然归并排序使用递归，这似乎是这里使用的方法。但是，我不确定。我们必须使用自然合并排序和二进制合并排序并报告结果并讨论发现的结果。

Answer 1

您帖子中的排序是自然合并排序。二元归并排序的工作方式类似于归并排序，只是在归并排序之前增加了使用二元插入排序的步骤。

这样做是为了结合插入排序对小数据集的效率和归并排序对大数据集的效率。

在此处查看“变体”部分:https://en.wikipedia.org/wiki/Insertion_sort#Variants

这也是一个相关的 SO 问题:Binary Merge sort & Natural Merge sort