3 ms·
Yes, Java as well as .Net implementations used recursive QuickSort (I think Java recently switched to Timsort?). The implementation however used only one recurs
by sytelus 11y ago
Yes, Java as well as .Net implementations used recursive QuickSort (I think Java recently switched to Timsort?). The implementation however used only one recursive call instead of two as in textbooks because second call is tail recursive and can be made iterative. This is however not done just to avoid recursion. With QuickSort you run risk of using up O(n) stack space in worse case. Making second call iterative allows to make sure recursion always occur on smaller partition thus guerenteeing O(lg n) space.