This is my point, the worst case of stack usage of the basic quick sort algorithm is O(n), not O(log n); O(log n) is the average case. Consider a quicksort alg

This is my point, the worst case of stack usage of the basic quick sort algorithm is O(n), not O(log n); O(log n) is the average case. Consider a quicksort algorithm that takes the first element in each partition and uses that as the pivot. When given sorted data it will iterate as: Notation: (left set) _pivot_ (right set) Input: 1 2 3 4 5 () _1_ (2 3 4 5) 1 is chosen as pivot, all elements in right set 1 () _2_ (3 4 5) 2 is chosen as pivot... 1 2 () _3_ (4 5) 1 2 3 () _4_ (5) Note that for each recursion we're construction the input with the aim of leaving one of the partitions empty, so that we only ever sort 1 element (the pivot) each iteration. So that's n-1 levels of recursion with n elements -> O(n) Even if you take the 'middle' (left-middle if even number) element as the pivot it's possible to construct a patalogical case:- Input: 4 2 1 3 5 () _1_ (4 2 3 5) 2 is next pivot for right partition 1 () _2_ (4 3 5) 3 is next pivot for right partition 1 2 () _3_ (4 5) 4 is next pivot as left of middle for even number of elements 1 2 3 () _4_ (5) ... Again, n-1 levels of recursion with n elements -> O(n) On the other point; I'm not saying that every implementation of quicksort out there is susceptible. I'm saying that there are quite a few implementations that are in common use that are just the basic quick sort algorithm and can be made to blow through available finite stack space given large enough datasets or even semi-pathalogical input cases. The majority of problems can be done away with by choosing a random pivot point from the set, that way it's very unlikely (but not impossible) to achieve a pathalogical case. However, such an implementation becomes indeterministic in that there's a very small but non-zero chance that the random pivots chosen will select items from the array in relative order and lead to too many levels of recursion. To me something that blows up only very rarely, and virtually impossible to replicate, is a nightmare to debug and fix. I'd much rather put the right algorithm in there to begin with to avoid this possibility completely. There are plenty of other tricks you can implement to avoid cases like this, e.g. checking that the pivot creates partitions with at least 10% of elements in; that greatly reduces the number of possible recursions But you'd be surprised at the number of sort implementations out there in the real world which are just implementations of the basic quicksort algorithm.