How does insert merge sorting work?

Question

I am currently studying sorting algorithms and have found a Merge Insertion Sort. I could hardly find anything for this, but only a few articles and links to books. Thus, this algorithm was discovered by Lester Ford Jr. and Selmer Johnson. This is partly described here: http://www2.warwick.ac.uk/fac/sci/dcs/teaching/material/cs341/FJ.pdf

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

What I currently have in the code is as follows:

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

++ , . , :

, : , , , 2 ^ n 2 ^ (n + 1) -1. , 8 15 .

, pend pend, 2 : 2 , 4 , b3 , {b1, a1, a2}. , b2 < a2, a2 , {b1, a1}, {b1, a1, b2}, , 3 , 2 , . , , 7 : b5 < a5, b5 {b1, a1, b2, a2, a3, b3, a4}, 7 ..

b , , 2 ^ n - 1. , @orlp: t(k) = (2^(k+1) + (-1)^k)/3. Jacobsthal; , , 66- Jacobsthal 64- . bk, bk, k . pend, , , Jacobsthal, ; , , , .