合并插入排序是如何工作的？

Question

我目前正在研究排序算法并找到了合并插入排序。我几乎找不到任何东西，但只有几篇论文和书籍参考。所以这个算法是由 Lester Ford, Jr. 和 Selmer Johnson 发现的。这里有部分描述：http : //www2.warwick.ac.uk/fac/sci/dcs/teaching/material/cs341/FJ.pdf

我现在的问题是了解插入部分的工作原理，以及 1、3、5、11 的编号顺序，在如何插入的解释中提到。看着好眼熟，就是想不起来是什么了。

到目前为止，我所拥有的代码是这样的：

//pointer to array, array size, element size, compare function pointer
void sort(void *data, size_t n, size_t s, int (*fcomp)(void*, void*))
{
  if(!data) return;
  if(n < 2 || s == 0) return;

  size_t i = 0, j = 0, k = 0, l = 0, r = 0, m = 0;

  void *be = malloc((n/2)*s); //elements greater in pair comparison
  void *le = malloc((n/2 + n%2)*s);//elements lesser in pair comparison
  void *mc = malloc(n*s); //main chain

  //compare pair-wise K_1:K_2, ... , K_N:K_N-1
  for(i = 0; i < n; i+=2)
  {
    if(fcomp(voidAdd(data, s, i), voidAdd(data, s, i+1)) >= 0)
    {
      //element at i bigger than i+1 so, put it in be and i+1 in le
      memcpy(voidAdd(be, s, k++), voidAdd(data, s, i), s);
      memcpy(voidAdd(le, s, j++), voidAdd(data, s, i+1), s);
    }
    else
    {
      //element i+1 bigger than i so put it in be and i in le
      memcpy(voidAdd(be, s, k++), voidAdd(data, s, i+1), s);
      memcpy(voidAdd(le, s, j++), voidAdd(data, s, i), s);
    }
  }

  sort(be, n/2, s, fcomp); //recursivly repeat process for bigger elements
  /*
  now we have chain a_1, ..., a_n/2 and b_1, ..., b_n/2 with a_i > b_i and
  a_1 < ... a_n/2
  */

  memcpy(mc, le, s); //insert b_1 into the main-chain
  memcpy(voidAdd(mc, s, 1), be, (n/2)*s); //copy a_1, ... a_n/2 in main chain
  //now we have b_1, a_1, ..., a_n/2 as main chain

  //start insertion here
  j = n/2 + 1;
  for(i = 1; i < n/2; i++)
  {
    k = ...;//number from sequence 1, 3, 5, 11, ...
  }

  memcpy(data, mc, n*s);
  free(mc);
  free(be);
  free(le);

}

从链接的pdf中写的内容来看，它现在需要通过二进制插入将b_3、b_2、b_5、b_4 ...插入主链，但我不确定如何准确地做到这一点以及他们从哪里获取这些数字.

Answer 1

本周我实际上用 C++ 实现了这个算法，并且能够理解插入部分是如何工作的。我不想重复自己的话，所以我会引用自己的话：

\n\n

\n

为了执行最少的比较次数，我们需要考虑以下关于二分搜索的观察：当元素数量为 2^n 时，对排序序列执行二分搜索所需的最大比较次数是相同的它是 2^(n+1)\xe2\x88\x921。例如，在 8 个或 15 个元素的排序序列中查找元素需要相同数量的比较。

\n

\n\n

基本上，在主链中插入第一个pend元素后，算法会采用最远的pend元素，需要进行 2 次比较：您需要 2 次比较才能插入少于 4 个元素，所以我们在论文中采用，因为我们可以将它插入到. 接下来，我们知道，所以我们可以插入到主链中，它要么是要么，这意味着我们将它插入到最多 3 个元素的链中，所以我们最多需要 2 次比较来插入它。接下来，我们需要一个最多可插入 3 次比较的元素，因此需要将其插入到最多 7 个元素的主链中：我们有，因此我们可以插入b3{b1, a1, a2}b2 < a2a2{b1, a1}{b1, a1, b2}b5 < a5b5{b1, a1, b2, a2, a3, b3, a4}恰好是 7 个元素的主链， ETC...

\n\n

下一个要挑选的待决 b将始终对应于您可以插入主链中的大小为 2^n - 1 的元素。Knuth 设法找到了 @orlp: 给出的生成公式t(k) = (2^(k+1) + (-1)^k)/3。生成的数字恰好对应于Jacobsthal 数字；该系列增长得如此之快，以至于您可以简单地缓存它们，第 66 个 Jacobsthal 数甚至无法容纳在 64 位整数中。一旦插入了这样的元素bk，您就可以以相反的顺序插入所有小于当前 Jacobsthal 编号的bk元素。如果排序末尾k还有待处理元素，但它们都没有对应于 Jacobsthal 编号的索引，只需将它们插入主链即可；插入顺序并不重要，因为无论插入顺序如何，插入其中任何一个所需的比较次数都应该相同。

\n