merge sort

merge_sort.cxx

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