Comment by virgilp
4 years ago
Actually, yeah, my original reply was dumb, I forgot quicksort :)
It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
4 years ago
Actually, yeah, my original reply was dumb, I forgot quicksort :)
It can be n*n for properly-sorted arrays too, depending on pivot selection (for randomized pivot selection, it's n log n).
Yes; random pivot selection is nlogn (unless you are very, very, statistically impossibly, unlucky. Or using very short arrays where it doesn't matter anyway).
But I'm pretty sure data sorted in either direction (i.e., 'reversed' or not, ascending or descending), and taking a pivot from either end, is n^2. It doesn't have to be reversed; you always end up with everything unsorted ending up on one side or the other of the pivot, with each recursive step being just one less comparison than the step prior, meaning it has N-1 + N-2 + ... + 1 comparisons regardless of which way the array is sorted, or N(N-1)/2 comparisons total (Gauss' formula but starting at one less than the total number of items N, since that's the number of comparisons each step), which is O(N^2). There is no cause where it's linear time, unless you are first iterating across the array to select the first pivot that is out of place (which may be a reasonable optimization, but can also be made to apply regardless of what direction the array is sorted).