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 
#include 
using namespace std;

// Insert sort O(n^2) time O(1) space
template 
void ins_sort(Iterator first, Iterator end) {
    for (Iterator cur = first; cur 
void merge(Iterator first, Iterator middle, Iterator last) {
    using T = typename iterator_traits::value_type;
    vector left(first, middle + 1);
    vector right(middle + 1, last + 1);
    left.push_back(0xFFFFFFF); // sentinel
    right.push_back(0xFFFFFFF);
    for (int i = 0, j = 0, k = 0; k 
void merge_helper(Iterator first, Iterator last) {
    if (first 
void mer_sort(Iterator first, Iterator end) {
    merge_helper(first, end - 1);
}

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

Testing code

```
#include
#include
#include
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<> distribution;
};

template
void print(vector v) {
for (auto x : v)
cout randgen(int max, int num) {
static Rand_int die{0, max};
vector 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]

-
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 < last1) && (first2 < last2)) {
        if (*first1 <= *first2) {
            *dst++ = *first1++;
        } else {
            *dst++ = *first2++;
        }
    }
    while (first1 < last1) *dst++ = *first1++;
    while (first2 < last2) *dst++ = *first2++;
}

StackExchange Code Review Q#64950, answer score: 3