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 минут, и он все еще работает! Даже список из 100 000 не так велик, поэтому:

1. Как я могу обрабатывать данные в миллиард данных?
2. это алгоритм сортировки (слияние и сортировка) занимает меньше времени на другом языке, таком как C#, python ... это проблема в языке haskell
3. Как я мог предсказать время выполнения алгоритма с использованием его сложности?

Answer 1

Худшее время случай быстрой сортировки п. Ваша реализация использует первый элемент в качестве шарнира, что приводит к производительности в худшем случае, когда вход сортируется (или отсортирован в обратном порядке).

Чтобы получить быструю сортировку выполнить в ожидаемой сложности п журнала п, вам нужно либо рандомизированное выбор поворота, или в случайном порядке перетасовать вход перед сортировкой.