## 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