Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
merge sort
// https://en.wikipedia.org/wiki/Merge_sort
#include <iostream>
#include <iomanip>
#include <cstddef>
#include <cassert>
using std::size_t;
/// @brief sort range [first, last)
void merge_sort(int * a, size_t first, size_t last);
/// @brief check what range [first, last) is sorted
bool is_sorted(const int * a, size_t first, size_t last);
/// @brief print range [first, last) of array `a`
void print(const char * title, const int * a, size_t first, size_t last);
int main(int argc, char** argv)
{
int A[] = {5, 2, 4, 6, 1, 3, 2, 6};
constexpr auto length_a = sizeof(A) / sizeof(A[0]);
print("origin[]", A, 0, length_a);
merge_sort(A, 0, length_a);
print("sorted[]", A, 0, length_a);
std::cout << "is_sorted(A) == " << std::boolalpha << is_sorted(A, 0, length_a) << std::endl;
return 0;
}
size_t split_range(size_t first, size_t last)
{
return (first + last) / 2;
}
void merge(int * a, size_t first, size_t middle, size_t last)
{
assert(a != nullptr);
auto sz = last - first;
auto tmp = new int [sz];
auto left = first;
auto right = middle;
for(size_t idx = 0; idx < sz; ++idx)
{
if (left < middle && (right >= last || a[left] < a[right]))
{
tmp[idx] = a[left];
++left;
}
else
{
tmp[idx] = a[right];
++right;
}
}
// copy data back
for(size_t idx = 0; idx < sz; ++idx)
{
a[first + idx] = tmp[idx];
}
delete [] tmp;
}
void merge_sort(int * a, size_t first, size_t last)
{
assert(a != nullptr);
if (first + 1 < last) // less whan two items in range
{
auto middle = split_range(first, last);
merge_sort(a, first, middle);
merge_sort(a, middle, last);
merge(a, first, middle, last);
}
}
bool is_sorted(const int * a, size_t first, size_t last)
{
assert(a != nullptr);
assert(first < last);
for (size_t idx = first; idx < last - 1; ++idx)
{
if (a[idx] > a[idx + 1])
{
return false;
}
}
return true;
}
void print(const char * title, const int * a, size_t first, size_t last)
{
assert(a != nullptr);
assert(first < last);
std::cout << title << " = {\n\t";
for (auto idx = first; idx < last; ++idx)
{
std::cout << a[idx] << ", ";
}
std::cout << "\n}\n";
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment