#include "tools.hpp"
std::vector<int> sort(size_t start, size_t length, const std::vector<int>& vec)
{
if(vec.size()==0 ||vec.size() == 1)
return vec;
vector<int> left,right;
size_t mid_point = vec.size()/2;
for(int i = 0 ; i < mid_point; ++i){left.emplace_back(vec[i]);}
for(int j = mid_point; j < length; ++j){ right.emplace_back(vec[j]);}
left = sort(start,mid_point,left);
right = sort(mid_point,length-mid_point,right);
return merge(left,right);
}
vector<int> merge(const vector<int>& a, const vector<int>& b)
{
vector<int> merged_a_b(a.size()+b.size(),0);
int i = 0;
int j = 0;
int k = 0;
int left_size = a.size();
int right_size = b.size();
while(i<left_size && j<right_size)
{
if(a[i]<b[j])
{
merged_a_b[k]=a[i];
i++;
}
else
{
merged_a_b[k]=b[j];
j++;
}
k++;
}
while(i<left_size)
{
merged_a_b[k]=a[i];
i++;
k++;
}
while(j<right_size)
{
merged_a_b[k]=b[j];
j++;
k++;
}
return merged_a_b;
}