Haskell schnelle Sortierkomplexität?

Question

I ausführen, um die unten schnelle Sortierung Haskell-Funktion (merge und Sortieralgorithmus verwendet wird):

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

Um die Laufzeit für diese eine wenig große Menge von Daten zu testen, I den folgenden Code ausführen:

qsort [100000,99999..0] 

Es dauert bis jetzt 40 min und es läuft noch! Selbst eine Liste von 100.000 ist nicht so groß, also:

1. Wie könnte ich mit einer Milliarde Daten umgehen?
2. ist dieser Sortieralgorithmus (merge und sort) braucht weniger Zeit in anderen Sprachen wie C#, Python ... ist das ein Problem in Haskell Sprache
3. Wie könnte ich die Laufzeit eines Algorithmus mit seiner Komplexität vorhersagen?

Answer 1

Der schlimmste Fall Zeit von Quicksort ist n. Ihre Implementierung verwendet das erste Element als Pivot, was zu einer Worst-Case-Leistung führt, wenn die Eingabe sortiert (oder umgekehrt sortiert) wird.

quicksort Um bei seiner erwarteten Komplexität von n log n auszuführen, benötigen Sie entweder randomisierten Pivot-Auswahl, oder zufällig den Eingang mischen vor dem Sortieren.