ネストの深いアルゴリズム

ところで、ネストが深いアルゴリズムといったら、batcher's odd-even mergesortを思い出す。

template <class Item>
void batchersort(Item a[], int l, int r)
 { int N = r-l+1;
   for (int p = 1; p < N; p += p)
    for (int k = p; k > 0; k /= 2)
     for (int j = k%p; j+k < N; j += (k+k))
      for (int i = 0; i < N-j-k; i++)
       if ((j+i)/(p+p) == (j+i+k)/(p+p))
        { Item &a0 = a[l+j+i], &a1 = a[l+j+i+k], t;
          if (a1 < a0) { t = a0; a0 = a1; a1 = t;}}
 }

上のは、某テキストからコピーしてきたのだけれど、ループが１つ不要じゃないか？ つまり、下のでいいんじゃない？

template <class Item>
void batchersort(Item a[], int l, int r)
 { int N = r-l+1;
   for (int p = 1; p < N; p += p)
    for (int k = p; k > 0; k /= 2)
     for (int i = k%p; i < N-k; i++)
      if (i/(p+p) == (i+k)/(p+p))
       { Item &a0 = a[l+i], &a1 = a[l+i+k], t;
         if (a1 < a0) { t = a0; a0 = a1; a1 = t;}}
 }

アルゴリズムに忠実に書くなら、こうなるのか？

template <class Item>
void batchersort(Item a[], int l, int r)
 { int N = r-l+1;
   for (int p = 1; p < N; p += p)
    for (int k = p; k > 0; k /= 2)
     for (int j = k%p, i = j; i < N-k; i++)
      if ((i-j)/(k+k) == (i+k-j)/(k+k) && i/(p+p) == (i+k)/(p+p))
       { Item &a0 = a[l+i], &a1 = a[l+i+k], t;
         if (a1 < a0) { t = a0; a0 = a1; a1 = t;}}
 }