プログラム：

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

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

  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--;
    }
  }
  /* left == right + 1になる */

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

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

#define N 1000000

int main() {
  int i, a[N];

  srandom(0); /* 乱数生成器を初期化 */
  for (i = 0; i < N; i++) {
    a[i] = random() % 100000000; /* 0から99999999までの乱数を生成 */
  }

  quicksort(&a[0], N);

  /* ソートされていることを確認 */
  for (i = 0; i < N - 1; i++) {
    if (a[i] > a[i + 1]) {
      printf("ERROR\n");
    }
  }

  quicksort(&a[0], N); /* もう1回ソートしてみると… */

  printf("qsort kadai 2 finished\n");
  return 0;
}

多かった誤答：「最小要素がpivotになってしまうので、
交換回数が増える(while文の中のif文のelse節がより頻繁に実行される)から」

then節（l++）とelse節（交換してr--）の差だけで何十倍も遅くなるわけがない！
実際にthen節のほうに2回交換する（ので元に戻る）コードを追加してみても、
そこまで遅くはならない（せいぜい2倍ぐらい）。

大まかな正答：「常に最小に近い要素がpivotになってしまうので、
分割が極端に偏ってしまい、再帰の回数が増えるから」

詳しい説明：

たとえば要素の数nが16で、配列aは次のようになっていたとする。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

1がpivotとなるから、while(left<=right){...}を実行した後のaは

1  3 4 5 6 7 8 9 10 11 12 13 14 15 16  2

となるので、空（要素が0個）の配列と

3 4 5 6 7 8 9 10 11 12 13 14 15 16  2
(n = 16-1-0 = 15)

に分割される。後者を新たなaとする再帰を考えると、3がpivotとなり、while文の後は

3  2  6 7 8 9 10 11 12 13 14 15 16  5 4

となるので、2のみ（要素が1個）の配列と

6 7 8 9 10 11 12 13 14 15 16  5 4
(n = 15-1-1 = 13)

に分割される。後者を新たなaとする再帰を考えると、6がpivotとなり、while文の後は

6  4 5  10 11 12 13 14 15 16  9 8 7

となるので、4 5（要素が2個）という配列と

10 11 12 13 14 15 16  9 8 7
(n = 13-1-2 = 10)

に分割される。後者を新たなaとする再帰を考えると、10がpivotとなり、while文の後は

10  7 8 9  15 16  14 13 12 11

となるので、7 8 9（要素が3個）という配列と

15 16  14 13 12 11
(n = 10-1-3 = 6)

に分割される。

このように、分割された大きいほうの配列に対する再帰を考えると、
要素の数が「ほぼ半分ずつに減っていく」のではなく、
「1回目は1つ減り、2回目は2つ減り、3回目は3つ減り、…」となる。
この再帰の深さをdとおくと、n-1-2-3-...-d ≒ 0すなわちdは√nのオーダーなので、
計算量はO(n log n)ではなくO(n√n)になる。

なお、このプログラムで最悪の場合は、aが

1 16 2 15 3 14 4 13 5 12 6 11 7 10 8 9

のようになっているケースである。大きいほうの配列に対する再帰を考えると

2 15 3 14 4 13 5 12 6 11 7 10 8 9 16
3 14 4 13 5 12 6 11 7 10 8 9 16 15
4 13 5 12 6 11 7 10 8 9 16 15 14
5 12 6 11 7 10 8 9 16 15 14 13
…

のように要素が1つずつしか減らない。このときの計算量はnの2乗のオーダーになる。