本当はむずかしいクイックソート（またクイズ）

アルゴリズム入門の代表的例題のような「クイックソート」ですが、意外と「罠」が少なくありません。例えば以下のような教科書的実装を考えます。

void quicksort(int *a, int n) {
  int tmp, pivot, left, right;

  if (n <= 1) return;

  pivot = a[0];
  left = 1;
  right = n - 1;
  while (left <= right) {
    if (a[left] < pivot) {
      left++;
    } else {
      tmp = a[left];
      a[left] = a[right];
      a[right] = tmp;
      right--;
    }
  }

  tmp = a[right];
  a[right] = a[0];
  a[0] = tmp;

  quicksort(&a[0], right);
  quicksort(&a[left], n - left);
}

この実装を用いて、例えば乱数をソートすると

> cat qsort-rand-100000000.c
#include <stdlib.h>
#define N 1000000
int main() {
  int i, a[N];
  srand(0);
  for (i = 0; i < N; i++) {
    a[i] = rand() % 100000000;
  }
  quicksort(&a[0], N);
  return 0;
}
> gcc -O3 qsort.c qsort-rand-100000000.c -o qsort-rand-100000000
> time ./qsort-rand-100000000
0.109u 0.001s 0:00.11 90.9%     0+0k 0+0io 0pf+0w

のようになりますし、典型的最悪ケースでは

> cat qsort-worst.c
#define N 1000000
int main() {
  int i, a[N];
  for (i = 0; i < N; i++) {
    a[i] = -i;
  }
  quicksort(&a[0], N);
  return 0;
}
> gcc -O3 qsort.c qsort-worst.c -o qsort-worst
> time ./qsort-worst
331.605u 0.019s 5:31.67 99.9%   0+0k 0+0io 0pf+0w

のようになります。
さて、では

#define N 1000000
int main() {
  int i, a[N];
  for (i = 0; i < N; i++) {
    a[i] = i;
  }
  quicksort(&a[0], N);
  return 0;
}

の実行時間はどれぐらいになるでしょうか？

#include <stdlib.h>
#define N 1000000
int main() {
  int i, a[N];
  srand(0);
  for (i = 0; i < N; i++) {
    a[i] = rand() % 100;
  }
  quicksort(&a[0], N);
  return 0;
}

はどうでしょうか。予想と結果およびその理由を考察してください。…などと書いてしまうと、またどこか他の方の授業のレポート課題と被るかもしれませんが。