Использование векторов для повышения производительности в Haskell

Я новичок в Haskell, и у меня есть вопрос о том, какие улучшения производительности можно получить, используя нечистые (изменяемые )структуры данных. Я пытаюсь собрать воедино несколько разных вещей, которые я слышал, поэтому, пожалуйста, потерпите меня, если моя терминология не совсем верна или есть небольшие ошибки.

Чтобы конкретизировать это, рассмотрим алгоритм быстрой сортировки (, взятый из вики Haskell ).

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

Это не «настоящая быстрая сортировка». «Настоящий» алгоритм быстрой сортировки находится в -месте, а это — нет. Это очень неэффективно для памяти.

С другой стороны, в Haskell можно использовать векторы для реализации быстрой сортировки по месту -. Пример приведен в этом ответе stackoverflow.

Насколько второй алгоритм быстрее первого? Нотация большого O здесь не поможет, потому что повышение производительности будет происходить за счет более эффективного использования памяти, а не за счет лучшего алгоритма (, верно? ). Я устал создавать несколько тестовых случаев самостоятельно, но у меня были проблемы с запуском.

Идеальный ответ дал бы некоторое представление о том, что теоретически делает алгоритм Haskell in -place быстрее, и пример сравнения времени выполнения на некотором наборе тестовых данных.