I know that quicksort has O(n log n) average
time complexity. A pseudo-quicksort (which is only a quicksort when you look at it from far enough away, with a suitably high level
of abstraction) that is often used to demonstrate the conciseness
of functional languages is as follows (given in Haskell):
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]
Okay, so I know this thing has problems. The biggest problem with this is that it does not sort in place, which is normally a big advantage
of quicksort. Even if that didn't matter, it would still take longer than a typical quicksort because it has to do two passes
of the list when it partitions it, and it does costly append operations to splice it back together afterwards. Further, the choice
of the first element as the pivot is not the best choice.
But even considering all
of that, isn't the average
time complexity
of this quicksort the same as the standard quicksort? Namely, O(n log n)? Because the appends and the partition still have linear
time complexity, even if they are inefficient.
