Talk:cpp/algorithm/partition
From cppreference.com
The example is awkward, why would you have two partition steps and the second one in the opposite direction?
- it's a fairly common variant of quicksort, which avoids useless recursion into subsequences where all elements are equivalent. Wikipedia says this is how Unix v7 qsort was implemented. --Cubbi (talk) 06:47, 17 December 2015 (PST)
May I ask why the possible implementation with BidrectionalIterator was deleted? Without this implementation, the time complexity can not reach std::distance(first, last) / 2. -- Zhiqing Xiao (talk) 18:59, 26 August 2016 (PDT)
- are you referring to this 2015 edit (later fixed up to actually do last-first)? Not sure if the editor is available to comment now. Perhaps it would be possible to set up a compact-enough possible implementation with tag dispatch to show how both complexity requirements are reached. --Cubbi (talk) 06:10, 29 August 2016 (PDT)
