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

// Insert sort O(n^2) time O(1) space
template <typename Iterator>
void ins_sort(Iterator first, Iterator end) {
for (Iterator cur = first; cur < end; ++cur) {
auto key = *cur;
Iterator ins = cur - 1;
for (; first <= ins && key < *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 <typename Iterator>
void merge(Iterator first, Iterator middle, Iterator last) {
using T = typename iterator_traits<Iterator>::value_type;
vector<T> left(first, middle + 1);
vector<T> right(middle + 1, last + 1);
left.push_back(0xFFFFFFF); // sentinel
right.push_back(0xFFFFFFF);
for (int i = 0, j = 0, k = 0; k <= last - first; ++k) {
if (left[i] < right[j]) first[k] = left[i++];
else first[k] = right[j++];
}
}

template <typename Iterator>
void merge_helper(Iterator first, Iterator last) {
if (first < 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 <typename Iterator>
void mer_sort(Iterator first, Iterator end) {
merge_helper(first, end - 1);
}

// Quick sort O(nlogn) time O(n) space
template <typename Iterator>
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 <= right) {
while (*left < pivot) ++left;
while (pivot < *right) --right;
if (left <= right) { swap(*left, *right); ++left; --right; }
}
quick_sort(first, right);
quick_sort(left, last);
}
}
template <typename Iterator>
void qck_sort(Iterator first, Iterator end) {
quick_sort(first, end - 1);
}


Testing code

#include <random>
#include <vector>
#include <iostream>
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 <typename T>
void print(vector<T> v) {
for (auto x : v)
cout << x << ' ';
cout << '\n';
}

vector<int> randgen(int max, int num) {
static Rand_int die{0, max};
vector<int> res(num);
for (int i = 0; i < 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] < 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 < last1) && (first2 < last2)) {
if (*first1 <= *first2) {
*dst++ = *first1++;
} else {
*dst++ = *first2++;
}
}
while (first1 < last1) *dst++ = *first1++;
while (first2 < last2) *dst++ = *first2++;
}

• Fixed sentinel with merge (I tested with data with largest valid value and it works now); I'll take a look at effective partitioning; qck_sort and mer_sort just wrap the respective sorts by passing end - 1 for last iterator (can you recommend a better way of dealing with end being 1 after last elem)? Oct 7, 2014 at 18:33
• It is against CR rules to edit the code: it invalidates the review. Consider rolling your changes back. You are welcome to post the new version in a follow-up question.
– vnp
Oct 7, 2014 at 18:36
• Ah, that would make sense; done. But my previous questions remain regarding end being 1 after last element Oct 8, 2014 at 0:10