Skip to content

Instantly share code, notes, and snippets.

@adamkorg adamkorg/mergesort_r.cpp
Last active Mar 28, 2019

Embed
What would you like to do?
Merge sort (recursive)
#include <iostream>
#include <vector>
template<class T>
void merge(std::vector<T>& vals, int l, int m, int r) {
//iterate through both left and right partitions, selecting
//the lowest value of each comparision.
std::vector<T> out;
int i=l, j=m;
while(out.size() <= r-l) {
if (j>r || vals[i]<vals[j])
out.push_back(vals[i++]);
else if (i>=m || vals[j]<vals[i])
out.push_back(vals[j++]);
}
for(int n=0; n<out.size(); n++)
vals[l+n] = out[n];
}
template<class T>
void merge_sort(std::vector<T>& vals, int l, int r) {
if (r-l < 1)
return;
int m = (l+r+1) / 2;
merge_sort(vals, l, m-1);
merge_sort(vals, m, r);
merge(vals, l, m, r);
}
template<class T>
void merge_sort(std::vector<T>& vals) {
merge_sort(vals, 0, vals.size()-1);
}
template <class T>
void print_v(const std::vector<T>& vals) {
for (auto val : vals)
std::cout << val << " ";
std::cout << std::endl;
}
int main()
{
std::vector<int> nums { 4,9,6,3,8,5,1,7 };
print_v(nums);
merge_sort(nums);
print_v(nums);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.