oaktree

Merge Sort - C++ (Rough)

Mar 22nd, 2016
126
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <cstdlib>
  5.  
  6. using namespace std;
  7.  
  8. void mergesort(vector<char>& vec) {
  9.     int n = vec.size();
  10.  
  11.     // recursion terminator
  12.     if (n <= 1) return;
  13.     else if (n == 2) {
  14.         if (vec[0] > vec[1]) {
  15.  
  16.             char tmp = vec[0];
  17.             vec[0] = vec[1];
  18.             vec[1] = tmp;
  19.            
  20.         }
  21.  
  22.         return;
  23.     }
  24.  
  25.     vector<char> left(vec.begin(), vec.begin() + n / 2);
  26.     vector<char> right(vec.begin() + n / 2, vec.end());
  27.     vec.erase(vec.begin(), vec.end()); // because we have copied the values to the partitions (left and right)
  28.  
  29.     mergesort(left); mergesort(right);
  30.  
  31.     int itr = 0;
  32.    
  33.     while(!left.empty() && !right.empty() && itr < n) {
  34.         if (left[0] < right[0]) {
  35.  
  36.             vec.push_back(left.front());
  37.  
  38.             left.erase(left.begin());
  39.         } else {
  40.  
  41.             vec.push_back(right.front());
  42.            
  43.             right.erase(right.begin());
  44.         }
  45.  
  46.         itr++;
  47.     }
  48.    
  49.     if (!left.empty()) {
  50.         vec.insert(vec.end(), left.begin(), left.end());
  51.     } else if (!right.empty()) {
  52.         vec.insert(vec.end(), right.begin(), right.end());
  53.     }
  54.  
  55. }
  56.  
  57. int main() {
  58.     cout << "give me a string" << endl;
  59.     string s; getline(cin, s);
  60.  
  61.     vector<char> vec(s.begin(), s.end());
  62.  
  63.     if (!vec.empty()) mergesort(vec);
  64.  
  65.     string str(vec.begin(), vec.end());
  66.  
  67.     cout << str << endl;
  68.     return 0;
  69. }
RAW Paste Data