SHARE
TWEET

Merge Sort STL Vectors

TwoOfDiamonds Jun 13th, 2013 38 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. void MergeSort(vector<int> &vec)
  2. {
  3.         //if the vector has more than 1 element
  4.         if(vec.size() > 1)
  5.         {
  6.                 //separate the vector into two equal vectors
  7.                 vector<int> left(vec.begin(), vec.begin() + vec.size() / 2);
  8.                 vector<int> right(vec.begin() + vec.size() / 2, vec.end());
  9.  
  10.                 //recursively call MergeSort for each part of the vector
  11.                 MergeSort(left);
  12.                 MergeSort(right);
  13.  
  14.                 //make room for the new elements to be added
  15.                 vec.clear();
  16.  
  17.                 //as long as both the left and the right vectors have elements
  18.                 //in them, put the smallest of each into vec one by one
  19.                 while (!left.empty() && !right.empty())
  20.                 {
  21.                         if(left[0] < right[0])
  22.                         {
  23.                                 vec.push_back(left[0]);
  24.                                 left.erase(left.begin());
  25.                         }
  26.                         else
  27.                         {
  28.                                 vec.push_back(right[0]);
  29.                                 right.erase(right.begin());
  30.                         }
  31.                 }
  32.  
  33.                 //if there are no more elements in the left vector
  34.                 // put all those from the right vector directly into vec
  35.                 while(left.empty() && !right.empty())
  36.                 {
  37.                         vec.push_back(right[0]);
  38.                         right.erase(right.begin());
  39.                 }
  40.  
  41.                 //the same when there are no more elements in the right vector
  42.                 while(!left.empty() && right.empty())
  43.                 {
  44.                         vec.push_back(left[0]);
  45.                         left.erase(left.begin());
  46.                 }
  47.  
  48.         }
  49.  
  50. }
RAW Paste Data
Top