Sorting algorithms with utility functions and iterators

Question

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

Answer 1

• 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++;
  }
  

• LemonPi: 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)?
• vnp: 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.
• LemonPi: Ah, that would make sense; done. But my previous questions remain regarding end being 1 after last element