A sorting algorithm that utilizes a divide-and-conquer approach to sorting an array of elements. It works by dividing the input array into smaller sub-arrays, sorting each sub-array recursively, and then merging the sorted sub-arrays back together into a single sorted array.

Time Complexity: O(nlogn)

void merge(vector<int> &arr, int from, int to, int middle)
{

    vector<int> newArray;
    int currentFrom = from;
    int currentTo = middle + 1;

    while (currentFrom <= middle && currentTo <= to)
    {
        if (arr.at(currentTo) < arr.at(currentFrom))
        {
            newArray.push_back(arr.at(currentTo));
            currentTo++;
        }
        else
        {
            newArray.push_back(arr.at(currentFrom));
            currentFrom++;
        }
    }

    while (currentFrom <= middle)
    {
        newArray.push_back(arr.at(currentFrom));
        currentFrom++;
    }

    while (currentTo <= to)
    {
        newArray.push_back(arr.at(currentTo));
        currentTo++;
    }

    int index = from;

    for (int i = 0; i < newArray.size(); i++)
    {
        arr.at(index) = newArray.at(i);

        index++;
    }
}

void merge_sort(vector<int> &arr, int from, int to)
{
    if (from < to)
    {
        int middle = (from + to) / 2;
        merge_sort(arr, from, middle);
        merge_sort(arr, middle + 1, to);
        merge(arr, from, to, middle);
    }
}