mergesort algorithm in C++

merge_sort.cc

#include <iostream>
#include <vector>

/**
 * Merges two sorted subarrays of arr[].
 * The first subarray is arr[low..mid].
 * The second subarray is arr[mid+1..high].
 *
 * @param arr The array to be sorted.
 * @param low The starting index of the first subarray.
 * @param mid The ending index of the first subarray.
 * @param high The ending index of the second subarray.
 */
void merge(std::vector<int> &nums, int low, int mid, int high)
{
    int left, right, tmp_idx = 0;
    int temp[high + 1];

    // merge the two subarrays into a temporary array based on the values
    left = low, right = mid + 1;
    while (!(left > mid) && !(right > high))
    {
        if (nums[left] < nums[right])
        {
            temp[tmp_idx++] = nums[left++];
            continue;
        }

        temp[tmp_idx++] = nums[right++];
    }

    // copy the remaining elements from the left subarray
    while (!(left > mid))
    {
        temp[tmp_idx++] = nums[left++];
    }

    // copy the remaining elements from the right subarray
    while (!(right > high))
    {
        temp[tmp_idx++] = nums[right++];
    }

    // copy the sorted elements into the original array
    for (unsigned int i = 0; i != tmp_idx; ++i)
    {
        nums[low + i] = temp[i];
    }
}

/**
 * Sorts the given vector using the merge sort algorithm.
 *
 * @param arr The vector to be sorted.
 * @param low The starting index of the range to be sorted.
 * @param high The ending index of the range to be sorted.
 */
void merge_sort(std::vector<int> &arr, int low, int high)
{
    if (!(low < high))
    { // "low" should always be less than "high"
        return;
    }

    // calculate mid index
    int mid = (low + high) / 2;

    // sort left half
    merge_sort(arr, low, mid);

    // sort right half
    merge_sort(arr, mid + 1, high);

    // merge the two halves
    merge(arr, low, mid, high);
}

int main(void)
{
    std::vector<int> arr = {2, 6, 4, 8, 12};

    // print original array
    std::cout << "Original array: ";
    for (auto &c : arr)
    {
        std::cout << c << " ";
    }

    merge_sort(arr, 0, arr.size() - 1);

    std::cout << "\nSorted array: ";
    for (auto &c : arr)
    {
        std::cout << c << " ";
    }

    return 0;
}