C++ Merge Sort

merge_sort.cpp

#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

// Implementation

void print_vector(std::vector<int> array, std::string title) {
    cout << title << ": " << "[";
    for(int i : array)
        cout << i << ", ";
    cout << "]" << endl;
}

std::vector<int> merge(std::vector<int> arr1, std::vector<int> arr2) {
    std::vector<int> temp(arr1.size() + arr2.size());
    arr1.insert(arr1.end(), arr2.begin(), arr2.end());
    std::sort(arr1.begin(), arr1.end());
    return arr1;
}

std::vector<int> sort(std::vector<int>& array) {
    if(array.size() < 2) { // base case
        return array;
    }
    auto half = int(array.size() / 2);
    auto first = vector<int>(array.begin(), array.begin() + half);
    auto second = vector<int>(array.begin() + half, array.end());

    auto first_ = sort(first);
    auto second_ = sort(second);
    auto res = merge(first_, second_);

    return res;
}


// Tests

void test_empty_array() {
    std::vector<int> empty;
    empty = sort(empty);
    assert(empty.empty() && "Test with empty array failed");
}

void test_single_element() {
    std::vector<int> single = {1};
    single = sort(single);
    assert(single[0] == 1 && "Test with single element failed");
}

void test_sorted_array() {
    std::vector<int> sorted = {1, 2, 3, 4, 5};
    sorted = sort(sorted);
    assert(std::is_sorted(sorted.begin(), sorted.end()) && "Test with sorted array failed");
}

void test_reverse_sorted_array() {
    std::vector<int> reverse_sorted = {5, 4, 3, 2, 1};
    reverse_sorted = sort(reverse_sorted);
    assert(std::is_sorted(reverse_sorted.begin(), reverse_sorted.end()) && "Test with reverse sorted array failed");
}

void test_large_array() {
    std::vector<int> large(1000);
    for (int i = 0; i < 1000; ++i) {
        large[i] = 1000 - i; // Create reverse order
    }
    large = sort(large);
    assert(std::is_sorted(large.begin(), large.end()) && "Test with large array failed");
}

void test_array_with_duplicates() {
    std::vector<int> duplicates = {2, 3, 2, 3, 2};
    duplicates = sort(duplicates);
    assert(std::is_sorted(duplicates.begin(), duplicates.end()) && "Test with array of duplicates failed");
}

void test_all_identical_elements() {
    std::vector<int> identical(10, 5); // 10 elements, all are 5
    identical = sort(identical);
    assert(std::is_sorted(identical.begin(), identical.end()) && "Test with all identical elements failed");
}


// Main

void run_all_tests() {
    test_empty_array();
    test_single_element();
    test_sorted_array();
    test_reverse_sorted_array();
    test_large_array();
    test_array_with_duplicates();
    test_all_identical_elements();
}

int main() {
    run_all_tests();
    std::cout << "All tests passed successfully!\n";
    return 0;
}