3 ms·

The implementations of non-recursive Quicksort and tree traversal are not impractical, just a little bit longer. By the way, are recursive versions of sorting

• 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.
• CJefferson 11y ago
  Certainly std::sort and friends are recursive in all C++ implementations I've looked at. In C++ it's hard to make the efficient and non-recursive. You can have a fixed-sized buffer (limits depth), or call malloc for a buffer (a single call to malloc can be more expensive than just doing the sort on the stack, and in general the C++ standard library tries hard to avoid mallocing).