Skip to content

Instantly share code, notes, and snippets.

@rayfix
Last active Dec 19, 2015
Embed
What would you like to do?
Simple merge sort implementation in C++. A little more polish. Thanks to feedback from @matt_dz
#include <iostream>
#include <vector>
#include <functional>
namespace rf {
template <typename T, typename Compare = std::less<T>>
std::vector<T> merge_sort(const std::vector<T>& input,
const Compare& compare = Compare())
{
size_t n = input.size();
if (n <= 1)
return input;
std::vector<T> output(n);
auto midpoint = begin(input) + (end(input) - begin(input))/2;
std::vector<T> left = merge_sort(std::vector<T>(begin(input), midpoint), compare);
std::vector<T> right = merge_sort(std::vector<T>(midpoint, end(input)), compare);
auto c1 = begin(left);
auto c2 = begin(right);
auto p = begin(output);
for ( ; p != end(output) && c1 != end(left) && c2 != end(right) ; ++p)
{
if (compare(*c1,*c2))
*p = *c1++;
else
*p = *c2++;
}
while (c1 != end(left))
*p++ = *c1++;
while (c2 != end(right))
*p++ = *c2++;
return output;
}
template <typename T>
void show(const std::vector<T>& vector)
{
for (const auto & element : vector)
std::cout << element << "\n";
}
}
int main(int argc, const char * argv[])
{
std::vector<int> input {9, 8, 7, 10, 2, 4, 1, 5, 6, 3};
std::cout << "Input" << std::endl;
rf::show(input);
auto sorted = rf::merge_sort(input);
std::cout << "Sorted" << std::endl;
rf::show(sorted);
auto reverse_sorted = rf::merge_sort(input, std::greater<decltype(input)::value_type>());
std::cout << "Reverse Sorted" << std::endl;
rf::show(reverse_sorted);
}
@rayfix

This comment has been minimized.

Copy link
Owner Author

@rayfix rayfix commented Jul 4, 2013

Added a defaulted function. lambda functions are awesome.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment