haskellクイックソートの複雑さ？

Question

私は（マージアルゴリズムを並べ替える使用して）以下のクイックソートHaskellの機能を実行します。

：

qsort []=[] 
qsort (x:xs) = 
    qsort smaller ++ [x] ++ qsort larger 
    where 
     smaller = [a | a <- xs , a<x ] -- edit 
     larger = [b | b <- xs , b>=x ] 

データのビット大きな量のために、このためのランタイムをテストするために、私は以下のコードを実行します

qsort [100000,99999..0] 

今のところ40分かかり、まだ走っています！たとえ10万のリストでさえそれほど大きいわけではありません：

1. 10億のデータをどのように扱うことができますか？
2. このソートアルゴリズム（マージとソート）は、C＃、Pythonなどの他の言語では時間がかかりません...これはhaskell言語の問題です
3. どのようにアルゴリズムの実行時間を予測することができますか？

Answer 1

クイックソートの最悪の場合の時間は、Nあります。インプリメンテーションでは、最初の要素をピボットとして使用します。これは、入力がソートされるとき（または逆順にソートされるとき）に最悪の場合のパフォーマンスをもたらします。

NログNのその期待複雑で実行するためにクイックソートを取得するには、いずれかの無作為化、ピボット選択を必要とする、またはランダムに並べ替えの前に入力をシャッフルします。