Skip to content

Instantly share code, notes, and snippets.

@coderodde
Last active January 14, 2019 02:48
Show Gist options
  • Save coderodde/862697e0aacce0d2a24cf26385ca67ef to your computer and use it in GitHub Desktop.
Save coderodde/862697e0aacce0d2a24cf26385ca67ef to your computer and use it in GitHub Desktop.
#include "mergesort.h"
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <random>
#include <vector>
using std::boolalpha;
using std::copy;
using std::cout;
using std::endl;
using std::equal;
using std::ostream_iterator;
using std::stable_sort;
using std::vector;
class CurrentTime {
std::chrono::high_resolution_clock m_clock;
public:
uint64_t milliseconds()
{
return std::chrono::duration_cast<std::chrono::milliseconds>
(m_clock.now().time_since_epoch()).count();
}
};
template<typename RandIt>
static void print_int_sequence(RandIt begin, RandIt end)
{
cout << *begin;
begin++;
while (begin != end)
{
cout << ' ' << *begin;
begin++;
}
cout << endl;
}
static vector<int> get_random_int_vector(size_t length)
{
vector<int> ret;
std::random_device rd;
std::mt19937 rng(rd());
std::uniform_int_distribution<int> uni;
for (size_t i = 0; i != length; ++i)
{
ret.push_back(uni(rng));
}
return ret;
}
static const size_t SEQUENCE_LENGTH = 10 * 1000 * 1000;
int main(int argc, const char * argv[]) {
vector<int> vec1 = get_random_int_vector(SEQUENCE_LENGTH);
vector<int> vec2(SEQUENCE_LENGTH);
vector<int> vec3(SEQUENCE_LENGTH);
copy(vec1.begin(), vec1.end(), vec2.begin());
copy(vec1.begin(), vec1.end(), vec3.begin());
CurrentTime ct;
auto start = ct.milliseconds();
mergeSort(vec1, 0, vec1.size() - 1);
auto end = ct.milliseconds();
cout << "OP mergeSort in " << (end - start) << " milliseconds." << endl;
start = ct.milliseconds();
mergeSort(vec2);
end = ct.milliseconds();
cout << "cr mergeSort in " << (end - start) << " milliseconds." << endl;
start = ct.milliseconds();
stable_sort(vec3.begin(), vec3.end());
end = ct.milliseconds();
cout << "stable_sort in " << (end - start) << " milliseconds." << endl;
bool agree = equal(vec1.begin(), vec1.end(), vec2.begin(), vec2.end()) &&
equal(vec1.begin(), vec1.end(), vec3.begin(), vec3.end());
cout << "Algorithms agree: " << boolalpha << agree << endl;
return 0;
}
#include <algorithm>
#include <iterator>
#include <vector>
template<typename T> void merge(std::vector<T> &vec, int left, int mid, int right )
{
int i=left;
int j=mid+1;
int k=0;
int size = (right - left) +1;
std::vector<T> result(size);
while(i <= mid && j <= right) result[k++] = (vec[i] < vec[j])? vec[i++] : vec[j++];
while(i <= mid) result[k++] = vec[i++];
while(j <= right) result[k++] = vec[j++];
for(k=0; k < size; k++)
{
vec[left+k] = result[k];
}
}
template<typename T> void mergeSort(std::vector<T> &vec, int left, int right)
{
// Base Case --- Left is greater than right, then don't execute.
if (left<right){
// get mid point.
int mid = left + (right-left)/2 ;
// recursive merge sort until array(half) is 1 in length.
mergeSort(vec, left, mid);
mergeSort(vec, mid+1, right);
// merge both arrays.
merge(vec, left, mid, right);
}
}
template<typename RandIt1, typename RandIt2>
void mergeSort(RandIt1 source_begin,
RandIt1 source_end,
RandIt2 target_begin,
RandIt2 target_end)
{
auto range_length = std::distance(source_begin, source_end);
if (range_length < 2)
{
return;
}
auto left_subrange_length = range_length >> 1;
mergeSort(target_begin,
target_begin + left_subrange_length,
source_begin,
source_begin + left_subrange_length);
mergeSort(target_begin + left_subrange_length,
target_end,
source_begin + left_subrange_length,
source_end);
std::merge(source_begin,
source_begin + left_subrange_length,
source_begin + left_subrange_length,
source_end,
target_begin);
}
template<typename RandIt>
void mergeSort(RandIt begin, RandIt end)
{
auto range_length = std::distance(begin, end);
if (range_length < 2)
{
return;
}
using value_type = typename std::iterator_traits<RandIt>::value_type;
std::vector<value_type> aux(begin, end);
mergeSort(aux.begin(), aux.end(), begin, end);
}
template<typename T>
void mergeSort(std::vector<T>& vec)
{
mergeSort(vec.begin(), vec.end());
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment