Merge sort (recursive)

mergesort_r.cpp

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