//
// 非再帰版マージソート(qsortとの時間比較付き)
//
// 考察: Nが大きくなればなるほどqsortとの差が開くが、これはデータキャッシュ・ミスによるものと思われる。
//

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

#define N 10000

int a[N], b[N], c[N]; /* 作業領域 */

int comp(const void *a, const void *b);
void qsort_sub(unsigned t);

int main(void)
{
  int i, j, x, y, x1, y1, f, t;
  DWORD t1;
  
  t = (unsigned)time(NULL);
  srand(t);
  for (i = 0; i < N; i++)
    a[i] = rand();
  
  t1 = timeGetTime();
  do {
    /* 部分ランへの分割 */
    x = y = f = 0; x1 = y1 = -1;

    for (i = 0; i < N; i++)
      if (f == 0) {
        if (x1 <= a[i])
          b[x++] = x1 = a[i];
        else {
          f = 1;
          c[y++] = y1 = a[i];
        }
      } else /* f == 1 */ {
        if (y1 <= a[i])
          c[y++] = y1 = a[i];
        else {
          f = 0;
          b[x++] = x1 = a[i];
        }
      }

      /* 部分ランのマージ(配列の交換がなくなったら終了) */
      x1 = y1 = j = f = 0;

      for (i = 0; i < N; i++)
        if (x1 == x) {
          a[j++] = c[y1++];
          if (f == 3);
          else if (f == 1)
            f = 3;
          else
            f = 2;
        } else if (y1 == y) {
          a[j++] = b[x1++];
          if (f == 3);
          else if (f == 2)
            f = 3;
          else
            f = 1;
        } else if (b[x1] <= c[y1]) {
          a[j++] = b[x1++];
          if (f == 3);
          else if (f == 2)
            f = 3;
          else
            f = 1;
        } else { /* b[x1] > c[y1] */
          a[j++] = c[y1++];
          if (f == 3);
          else if (f == 1)
            f = 3;
          else
            f = 2;
        }
      /* ソート済みになったかチェック */
//      f = 0;
//      for (i = 0; i < N - 1; i++)
//        if (a[i] > a[i + 1]) {
//          f = 1;
//          break;
//        }
  } while (f == 3);

//  printf("a = ");
//  for (i = 0; i < N; i++)
//    printf("%d ", a[i]);
//  putchar('\n');
  
  printf("%u ms\n", timeGetTime() - t1);
  
  qsort_sub(t);
  
  return 0;
}

int comp(const void *a, const void *b)
{
  return *(int *)a - *(int *)b;
}

void qsort_sub(unsigned t)
{
  DWORD t1;
  int i;

  srand(t);
  for (i = 0; i < N; i++)
    a[i] = rand();
  
  t1 = timeGetTime();

  qsort(a, N, sizeof(int), comp);

  printf("%u ms\n", timeGetTime() - t1);
}

>非再帰版のマージソートプログラムを作っています。再帰版のマージソート
>はとても速いのですが、非再帰版が思うように速度が出ません。
>データの個数が2^Nでなくても、奇数でもソートできるようにしたいの
>でこのようなプログラムにしたのですが、効率が悪いのでしょうか？

>// 考察: Nが大きくなればなるほどqsortとの差が開くが、これはデータキャッシュ・ミスによるものと思われる。
理想はO(NlogN)ですけど、
whileの中にfor文が2つあるからなんて感じで
O(2NlogN)とかになってる可能性はありませんか？
（定数は消えるのでそれでもO(NlogN)と書くのが正しいですが。）

O(2NlogN)なら
データ数4倍→実行時間16倍
データ数10倍→実行時間66倍
になるはずです。

で、私の環境で実測したところ
データ数10000→500ms
データ数40000→6500ms→実行時間13倍
データ数100000→46000ms→実行時間90倍

O(2NlogN)説はそれほど外れてもいない気がします。
同じデータサイズでクイックソートが理想値出すなら
キャッシュよりプログラム疑ったほうがいいです。経験的に。
あとコンパイラも疑いたくもなるけどまず自分のミス。

ちなみに経験的にというのは、
昔バブルソートで書かれたプログラムをクイックソートで書き直せという課題がでて
バルブソート数百秒→クイックソート1.5秒にしてやったぜ！クイック最高！
とか思ってたら「クイックならまず1秒かかりません」とか言われて
書き直したらその通りだったことが。
間違ったクイックっぽいなにかを書いてたんですね。
なんとなく今回もその臭いがします。

あぁ、なんか昔を思い出してしまった（涙）
せっかくなので私なりのマージソートおいときます。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>

#define N 10000

int a[N],b[N];

int *merge_sort(void){
    int cut_size,base;
    int i,j,i_max,j_max,tp;
    
    int *data = a;
    int *tmp = b;//tmp=作業領域
    int *p;
    int k;
    for(cut_size=1;cut_size < N;){//このループがlogN
        cut_size *= 2;//分割してるサイズ
        tp=0;//tmp用インデックス
        for(base = 0;base < N;base += cut_size){//N^2に見えてただのN
            i = base;
            i_max = j = base + cut_size/2;
            j_max = base + cut_size;
            if(i_max >= N){//ここと
                while(i < N) tmp[tp++] = data[i++];
                break;
            }
            if(j_max > N) j_max = N;//ここが「データの個数が2^Nでなくても、奇数でもソート」にあたる.
            for(;;){
                if(data[i] > data[j]){
                    tmp[tp] = data[i];
                    tp++;i++;
                    if(i >= i_max){//iが終わりなら
                        while(j < j_max) tmp[tp++] = data[j++];//jを全部
                        break;
                    }
                }
                else{
                    tmp[tp] = data[j];
                    tp++;j++;
                    if(j >= j_max){
                        while(i < i_max) tmp[tp++] = data[i++];
                        break;
                    }
                }
            }
        }
        p = tmp;//データと作業領域の入れ替え
        tmp = data;
        data = p;
    }
    return data;//a[N]かb[N]かわからんが返ったほうがソート済み
}

int main(){
    int t1,t2,i;
    srand(time(NULL));
    for (i = 0; i < N; i++) a[i] = rand();
    t1 = timeGetTime();
    
    merge_sort();
    
    t2 = timeGetTime();
    printf("%u ms\n",t2-t1);
    
    return 0;
}