How does Merge Insertion sort work?

Question

I am currently looking into sorting algorithms and found Merge Insertion Sort. I could barely find anything for it, but only a few papers and references to Books. So this algorithm was discovered by Lester Ford, Jr. and Selmer Johnson. It's partly described here: http://www2.warwick.ac.uk/fac/sci/dcs/teaching/material/cs341/FJ.pdf

My problem right now is understanding how the insertion part works and additionally what number sequence the 1, 3, 5, 11 is, mentioned in the explanation how to insert. It looks so familiar, but I just can't remember what it was.

What I have as of now code-wise is like that:

//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);

}

From what is written in the linked pdf, it needs to insert b_3, b_2, b_5, b_4 ... into the main chain now with binary insertion, but I'm not sure how to do that exactly and where they take these numbers from.

Stanhope

The numbers are explained in your PDF, and take the form t(k) = (2^(k+1) + (-1)^k)/3 where ^ is the power operator. – Nitroglycerin

wow, how did I not notice that... thank you for pointing this out! – Stanhope

this could help : youtube.com/watch?v=XaqR3G_NVoo ^^ – Aldric

@PandaCool Careful: mergesort and merge-insertion sort are different algorithms :p – Gusella

Answer 1

I actually implemented this algorithm in C++ this week and was able to understand how the insertion part worked. I don't really want to repeat myself, so I will quote myself instead:

To perform a minimal number of comparisons, we need to take into account the following observation about binary search: the maximal number of comparisons needed to perform a binary search on a sorted sequence is the same when the number of elements is 2^n and when it is 2^(n+1)−1. For example, looking for an element in a sorted sequence of 8 or 15 elements requires the same number of comparisons.

Basically, after having inserted the first pend element in the main chain, the algorithm takes the farthest pend element for which 2 comparisons need to be made: you need 2 comparisons to insert in less than 4 elements, so we take b3 in the paper, because we can insert it in {b1, a1, a2}. Next, we know that b2 < a2 so we can insert a2 in the main chain which will either be {b1, a1} or {b1, a1, b2}, which means that we insert it in a chain of at most 3 elements, so we need at most 2 comparisons to isert it. Next, we need an element that will be insertable with at most 3 comparisons, so it needs to be inserted in a main chain of at most 7 elements: we have b5 < a5, so we can insert b5 in {b1, a1, b2, a2, a3, b3, a4} which happens to be a main chain of 7 elements, etc...

The next pend b to pick will always correspond to an element you can insert in a main chain whose size is 2^n - 1. Knuth managed to find the generating formula given by @orlp: t(k) = (2^(k+1) + (-1)^k)/3. The generated numbers happen to correspond to Jacobsthal numbers; the series grows so fast that you can simply cache them, the 66th Jacobsthal number doesn't even fit in a 64-bit integer. Once you have inserted such an element bk, you can insert in reverse order all the bk elements for which k is less than the current Jacobsthal number. If you have pend elements left at the end of the sort but none of them has an indice corresponding to a Jacobsthal number, just insert them in the main chain; the order of insertion shouldn't matter since the number of comparisons needed to insert any of them should be the same regardless of the insertion order.

Gusella

alright, thanks! My biggest problem understanding how it worked was how to keep the sub lists' order in sync, as described in the book. I'll have a look and see how you solved this. – Stanhope

@pfannkuchen_gesicht Basically, I created a main chain lists of elements and a pend list of nodes where each node contains and element and an iterator to the higher element in the main chain list. It allows to know the upper bound of the insertion whenever you need to insert a pend element. – Gusella