3 ms·
QuickSort using middle element or median should perform optimally no? The middle (median) element in a sorted array has only less elements on the left and grea
by magicalhippo 7y ago
QuickSort using middle element or median should perform optimally no?
The middle (median) element in a sorted array has only less elements on the left and greater elements on the right, so the first pass of the quicksort would do nothing and not recurse further.
Or am I missing something?
- jonsen 7y agoTry this 4 3 2 1 5 9 8 7 6
- magicalhippo 7y agoI should have stayed in bed today... Still, probably faster to incorporate a monotonic check in a quicksort first pass, than run a bubble-sort pass which probably won't help much anyway?
- gpderetta 7y agoIntrosort, which used by the C++ standard libraries, switches from quicksort to heapsort for the (sub)partition for which has exceeded the expected recursion depth, so it is guaranteed to run in worst case O(nlogn) for all inputs. edit: which means it does not need a do nothing first pass and takes mitigating actions only in the worst case.