Sorting algorithms with utility functions and iterators My implementation of insertion, merge, and quick sort, with some utility testing functions. I just wanted to know how I can improve the efficiency and general cleanliness of my code.

(note: I know C++ has partition, but I want to do most of the implementation myself)

In particular, my main algorithms take iterators [first, last], but STL container's v.begin() and v.end() go 1 over the last element, so I have wrappers that call the main algorithm with first and end - 1.

How can I restructure this into the main algorithm (if that would be better)?

#include &lt;iterator&gt;
#include &lt;vector&gt;
using namespace std;

// Insert sort O(n^2) time O(1) space
template &lt;typename Iterator&gt;
void ins_sort(Iterator first, Iterator end) {
    for (Iterator cur = first; cur &lt; end; ++cur) {
        auto key = *cur;
        Iterator ins = cur - 1;
        for (; first &lt;= ins &amp;&amp; key &lt; *ins; --ins)
            *(ins + 1) = *ins;    // move 1 to right until correct position's found
        *(ins + 1) = key;
    }
}

// Merge sort O(nlogn) time O(n) space
template &lt;typename Iterator&gt;
void merge(Iterator first, Iterator middle, Iterator last) {
    using T = typename iterator_traits&lt;Iterator&gt;::value_type;
    vector&lt;T&gt; left(first, middle + 1);
    vector&lt;T&gt; right(middle + 1, last + 1);
    left.push_back(0xFFFFFFF); // sentinel
    right.push_back(0xFFFFFFF);
    for (int i = 0, j = 0, k = 0; k &lt;= last - first; ++k) {
        if (left[i] &lt; right[j]) first[k] = left[i++];
        else first[k] = right[j++];
    }
}

template &lt;typename Iterator&gt;
void merge_helper(Iterator first, Iterator last) {
    if (first &lt; last) {
        Iterator pivot = first + (last - first)/2;   // half way point rounded down
        merge_helper(first, pivot);
        merge_helper(pivot + 1, last);
        merge(first, pivot, last);
    }
}

template &lt;typename Iterator&gt;
void mer_sort(Iterator first, Iterator end) {
    merge_helper(first, end - 1);
}


// Quick sort O(nlogn) time O(n) space
template &lt;typename Iterator&gt;
void quick_sort(Iterator first, Iterator last) {
    if (last - first &gt; 0) {
        auto pivot = *(first + (last - first) / 2); 
        Iterator left {first};
        Iterator right {last};
        while (left &lt;= right) {
            while (*left &lt; pivot) ++left;
            while (pivot &lt; *right) --right;
            if (left &lt;= right) { swap(*left, *right); ++left; --right; }
        }
        quick_sort(first, right);
        quick_sort(left, last);
    }
}
template &lt;typename Iterator&gt;
void qck_sort(Iterator first, Iterator end) {
    quick_sort(first, end - 1);
}


Testing code

#include &lt;random&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;
using namespace std;

class Rand_int {
public:
    Rand_int(int low, int high) : distribution{low, high} {
    }
    int operator()() {
        return distribution(engine);
    }

private:
    default_random_engine engine;
    uniform_int_distribution&lt;&gt; distribution;
};

template &lt;typename T&gt;
void print(vector&lt;T&gt; v) {
    for (auto x : v)
        cout &lt;&lt; x &lt;&lt; ' ';
    cout &lt;&lt; '\n';
}

vector&lt;int&gt; randgen(int max, int num) {
    static Rand_int die{0, max};
    vector&lt;int&gt; res(num);
    for (int i = 0; i &lt; num; ++i)
        res[i] = die();
    return res;
}
There are few problems with merge: 

There is no guarantee that T can be constructed from an integral constant (how about sorting strings?). Even if it could, 0xFFFFFFF (BTW, what is this number?) is not necessarily a largest possible value (e.g.T could be 64 bit wide, or 16 bit wide); besides this value may legitimately belong to user data. Bottom line it, using an artificial sentinel is wrong.

(left[i] &lt; right[j]) condition breaks merge sort stability (which is very important reason of using merge sort in the first place).

Calculating pivot as  first + (last - first)/2 assumes a random access iterator, which rules out merge sorting linked lists (which is a second important reason for merge sort to be used). Take a look at std::distance and std::advance.
C++ has partition for a reason: it is very important algorithm of its own. I strongly recommend to factor it out as a function, and call it from quick_sort.
I don't see the reason for qck_sort and mer_sort to exist.

Take a look on how all std:: algorithms operate on semi-open ranges. One of the reasons for that is that last (in STL sense) serves as a natural sentinel. For example, merging may look along the lines of

void merge(I first1, I last1, I first2, I last2, O dst)
{
    while ((first1 &lt; last1) &amp;&amp; (first2 &lt; last2)) {
        if (*first1 &lt;= *first2) {
            *dst++ = *first1++;
        } else {
            *dst++ = *first2++;
        }
    }
    while (first1 &lt; last1) *dst++ = *first1++;
    while (first2 &lt; last2) *dst++ = *first2++;
}