Quote:
Shhh, don't give away the ending.
Good he did because I'm not willing to correct this algorithm :P. And actually it works but not for 10k elements (stack overflow) :)
Quote:
Shhh, don't give away the ending.
Quote:Original post by loufoque
Sorting 10k elements shouldn't cause a stack overflow [...] quicksort only requires logarithmic memory usage.
Quote:Original post by DevFredNo. Quicksort only requires logarithmic memory usage, even in the worst-case situations: whenever you split the interval around a pivot, recursively sort the smaller half, then tail-recurse on the larger half. Since tail recursion (either compiler-enforced or hand-optimized) never uses stack space, only the recursion on the smaller half matters, which results in worst-case logarithmic stack usage.
In the best case, yes. But imagine every pivot element you chose is the worst one (e.g. the minimum or maximum of the range to be sorted). Then you need linear memory usage.