Псевдо -временная сложность быстрой сортировки

Я знаю, что быстрая сортировка имеет O(n log n)среднюю временную сложность. Псевдо-быстрая сортировка (, которая является быстрой сортировкой только тогда, когда вы смотрите на нее достаточно далеко, с достаточно высоким уровнем абстракции ), который часто используется для демонстрации краткости функциональных языков, выглядит следующим образом (. ] дано в Haskell):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

Итак, я знаю, что у этой штуки есть проблемы. Самая большая проблема заключается в том, что он не сортируется на месте, что обычно является большим преимуществом быстрой сортировки. Даже если бы это не имело значения, это все равно заняло бы больше времени, чем обычная быстрая сортировка, потому что она должна выполнить два прохода по списку при его разбиении и выполнять дорогостоящие операции добавления, чтобы впоследствии соединить его вместе. Далее, выбор первого элемента в качестве опорного — не лучший выбор.

Но даже учитывая все это , разве средняя временная сложность этой быстрой сортировки не такая же, как у стандартной быстрой сортировки? А именно, O(n log n)? Потому что добавления и разделы по-прежнему имеют линейную временную сложность, даже если они неэффективны.