title: why do std::sort and partial_sort require random-access iterators?
body: <p>I was wondering why does the c++ standard require that <code>std::sort</code> should only take random-access iterators? I don't see the advantage, since both <a href="http://www.cplusplus.com/reference/algorithm/sort/" rel="nofollow noreferrer">std::sort</a> and <a href="http://www.cplusplus.com/reference/list/list/sort/" rel="nofollow noreferrer">std::list::sort</a> have a complexity of <code>N*log(N)</code>. Restricting <code>std::sort</code> to random-access iterators (RAI) seems to have made it necessary to write a separate function for lists with the same complexity. </p>
  
  <p>The same applies to <code>partial_sort</code>, where the non-RAI counter-part for list <a href="https://stackoverflow.com/questions/217073/partial-sort-of-stdlist">is simply missing</a> to this day.</p>
  
  <p>Is this design because people used variants of <code>quick_sort</code> to implement <code>std::sort</code> historically?</p>
  
  <p>If there is advantage for writing sort algorithms on RAI containers, would it better to make <code>std::sort</code> more general, and let RAI containers like <code>std::vector</code> provide specialized <code>v.sort</code>?</p>