[解決済み] なぜHaskellのクイックソートは "真の "クイックソートではないのか？

質問

Haskellのウェブサイトでは、非常に魅力的な5行の クイックソート関数 を紹介しています。

quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

また、これらには "C"での真のクイックソート。 .

// To sort array a[] of size n: qsort(a,0,n-1)

void qsort(int a[], int lo, int hi) 
{
  int h, l, p, t;

  if (lo < hi) {
    l = lo;
    h = hi;
    p = a[hi];

    do {
      while ((l < h) && (a[l] <= p)) 
          l = l+1;
      while ((h > l) && (a[h] >= p))
          h = h-1;
      if (l < h) {
          t = a[l];
          a[l] = a[h];
          a[h] = t;
      }
    } while (l < h);

    a[hi] = a[l];
    a[l] = p;

    qsort( a, lo, l-1 );
    qsort( a, l+1, hi );
  }
}

Cバージョンの下にあるリンクは、以下のようなページへの誘導です。 'Introduction で引用されているクイックソートは "real" クイックソートではなく、c のコードのように長いリストに対してスケールしない'.

なぜ上記のHaskell関数は真のクイックソートではないのでしょうか？どのようにして、より長いリストに対してスケールしないのでしょうか？

どのように解決するのですか？

真のクイックソートは2つの美しい側面を持っています。

1. 分割と征服：問題を2つの小さな問題に分割します。
2. 要素をインプレースで分割します。

Haskellの短い例では、(1)は実演していますが、(2)は実演していません。(2)がどのように行われるかは、そのテクニックをまだ知らない人には明白ではないかもしれません!