title: Sorting a std::vector which has parts of it sorted (formed by concatenation of sorted vectors)
body: <p>I have an std::vector as one of the inputs for an API i am exposing. 
  I know that the user of this API can send a huge vector, but that vector was formed by concatenation of sorted vectors. This means that the vector that I get is formed from a number of sorted vectors.</p>
  
  <p>I need to sort this vector. 
  I would like to know which sorting algorithm is best suited. 
  I would prefer an in-place sorting algo like merge or quick as I dont want to take up more memory (the vector is already a huge one).</p>
  
  <p>Also would it be better to change the API interface to accept N sorted vectors and then do the N-way merging myself. I dont want to go with this unless the saving is really huge. 
  Also while doing N-way merge I would want to do it in-place if possible. </p>
  
  <p>So ideally i would prefer the approach where i use some ready sort algorithm on the big vector (as that would be simpler I feel).</p>