Implementare il merge sort in C++

Da Wikipedia:

Il merge sort è un algoritmo di ordinamento basato su confronti che utilizza un processo di risoluzione ricorsivo, sfruttando la tecnica del Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola. Fu inventato da John von Neumann nel 1945. Una descrizione dettagliata e un'analisi della versione bottom-up dell'algoritmo apparve in un articolo di Goldstine e Neumann già nel 1948.

Ovviamente possiamo implementarlo in tutti i linguaggi che vogliamo.

Qui sotto un esempio in C++:

#include <iostream>

using namespace std;

void merge(int array[], int const left, int const mid, int const right)
{
    auto const arrayOne = mid - left + 1;
    auto const arrayTwo = right - mid;
    auto *leftArray = new int[arrayOne];
    auto *rightArray = new int[arrayTwo];
    auto indexArrayOne = 0;
    auto indexArrayTwo = 0;
    int indexMergedArray = left;

    for (auto i = 0; i < arrayOne; i++)
    {
        leftArray[i] = array[left + i];
    }

    for (auto j = 0; j < arrayTwo; j++)
    {
        rightArray[j] = array[mid + 1 + j];
    }

    while (indexArrayOne < arrayOne && indexArrayTwo < arrayTwo)
    {
        if (leftArray[indexArrayOne] <= rightArray[indexArrayTwo])
        {
            array[indexMergedArray] = leftArray[indexArrayOne];
            indexArrayOne++;
        }
        else
        {
            array[indexMergedArray] = rightArray[indexArrayTwo];
            indexArrayTwo++;
        }
        indexMergedArray++;
    }

    while (indexArrayOne < arrayOne)
    {
        array[indexMergedArray] = leftArray[indexArrayOne];
        indexArrayOne++;
        indexMergedArray++;
    }

    while (indexArrayTwo < arrayTwo)
    {
        array[indexMergedArray] = rightArray[indexArrayTwo];
        indexArrayTwo++;
        indexMergedArray++;
    }

    delete[] leftArray;
    delete[] rightArray;
}

void mergeSort(int array[], int const begin, int const end)
{
    if (begin >= end)
    {
        return;
    }

    auto mid = begin + (end - begin) / 2;

    mergeSort(array, begin, mid);
    mergeSort(array, mid + 1, end);
    merge(array, begin, mid, end);
}

void printArray(int arr[], int size)
{
    for (auto i = 0; i < size; i++)
    {
        cout << arr[i] << " ";
    }
}

int main()
{
    int arr[] = {13, 78, 99, 500, 1, 3};
    auto arr_size = sizeof(arr) / sizeof(arr[0]);

    cout << "ARRAY ORIGINALE:\n";
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    cout << "\nARRAY ORDINATO:\n";
    printArray(arr, arr_size);

    return 0;
}

Enjoy!