merge sort c++ github
#include "tools.hpp" /* >>>>>>>> (Recursive function that sorts a sequence of) <<<<<<<<<<<< >>>>>>>> (numbers in ascending order using the merge function) <<<< */ 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; //===> creating left and right vectors size_t mid_point = vec.size()/2; //===> midle point between the left vector and the right vector for(int i = 0 ; i < mid_point; ++i){left.emplace_back(vec[i]);} //===> left vector for(int j = mid_point; j < length; ++j){ right.emplace_back(vec[j]);} //===> right vector left = sort(start,mid_point,left); //===> sorting the left vector right = sort(mid_point,length-mid_point,right);//===> sorting the right vector return merge(left,right); //===> all the function merge to merge between the left and the right } /* >>>>> (function that merges two sorted vectors of numberss) <<<<<<<<< */ vector<int> merge(const vector<int>& a, const vector<int>& b) { vector<int> merged_a_b(a.size()+b.size(),0); // temp vector that includes both left and right vectors 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; }