• API
• FAQ
• Tools
• Trends
• Archive
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