C++ Merge Sort Algorithm
#include <random> #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> merge_sort(const vector<int>& input) { if(input.size()<=1) return input; vector<int> output(input.size()); //Split Vector// int midpoint=0.5*input.size(); vector<int> input_left(input.begin(),input.begin()+midpoint); vector<int> input_right(input.begin()+midpoint,input.end()); input_left=merge_sort(input_left); input_right=merge_sort(input_right); merge(input_left.begin(),input_left.end(),input_right.begin(),input_right.end(),output.begin()); return output; } int main(){ //Create unsorted vector of ints vector<int> unsorted(40); iota(unsorted.begin(),unsorted.end(),-20); shuffle(unsorted.begin(),unsorted.end(),default_random_engine()); //Perform merge_sort// vector<int> sorted=merge_sort(unsorted); //Display results// cout << "Unsorted: " << endl; for(auto value:unsorted) cout << value << " "; cout << endl; cout << "Sorted: " << endl; for(auto value:sorted) cout << value << " "; cout << endl; }
stdout
Unsorted:
-2 14 7 -15 -9 -17 -8 -1 13 1 -10 -7 16 -19 6 2 -12 -11 8 -18 -14 10 5 4 17 12 15 -16 -5 18 -4 -3 -6 -20 0 3 9 -13 11 19
Sorted:
-20 -19 -18 -17 -16 -15 -14 -13 -12 -11 -10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19