title: How is sort for std::deque implemented?
body: <p>Not so far I've learned how <code>std::deque</code> is implemented under the hood, and discovered that it's something like an array of pointers to n-byte arrays, where the data is actually stored. So now I have a couple of questions related to deques.</p>
  
  <p>A picture that describes my current knowledge about it's structure:<img src="https://i.stack.imgur.com/dbPA6.jpg" alt="enter image description here"></p>
  
  <p>The questions are:</p>
  
  <ol>
  <li><p>When a <code>push_front</code> operation is being performed and there is no free space in Data Block 0, a new Data Block is allocated on heap and a pointer to this freshly allocated memory is inserted into 'Map' array like in ordinary array -- in O(number_of_blocks) time, yes?</p></li>
  <li><p>How to sort this beast? Can't imagine anything better then copy all the data into array, sort it, and then put it back. But this approach requires O(n) auxiliary memory... But! <code>std::sort</code> provides similar interface for sorting both <code>std::vector</code> and <code>std::deque</code>. How are different algoritms for different data structures implemented? Using a template specialization? If so, why <code>std::list</code> can't be sorted using <code>std::sort</code>?
  Or, maybe, <code>std::sort</code> doesn't care about internal structure of this containers and just uses iterators and methods, that are similar in both <code>std::vector</code> and <code>std::deque</code> (like <code>operator[]</code>, <code>size()</code>, etc)? This idea sounds reasonable and an answer to "why can't <code>std::sort</code> sort <code>std::list</code>?" becomes evident.</p></li>
  <li><p>How are the sizes of data blocks being chosen? You'll say <em>"It's implementation dependent"</em>, but please tell more about different implementations and motivation behind solutions.</p></li>
  </ol>
  
  <p>Need clarifications here.
  Thanks.</p>