MergeSort.cpp

#include <iostream>
using namespace std;

// Funzione per fondere due sotto-array ordinati in uno unico ordinato
template <typename T>
void merge(T* arr, const size_t& start, const size_t& mid, const size_t& end) {
    // Calcolo delle dimensioni dei due sotto-array
    size_t leftsize = mid - start + 1;
    size_t rightsize = end - mid;

    // Allocazione dinamica dei due sotto-array temporanei
    T* leftarr = new T[leftsize];
    T* rightarr = new T[rightsize];

    // Copio la parte sinistra dell'array originale dentro leftarr
    for (size_t i = 0; i < leftsize; i++) {
        leftarr[i] = arr[i + start];
    }

    // Copio la parte destra dell'array originale dentro rightarr
    for (size_t i = 0; i < rightsize; i++) {
        rightarr[i] = arr[i + mid + 1];
    }

    // Indici per scorrere i sotto-array e l'array originale
    size_t leftindex = 0;
    size_t rightindex = 0;
    size_t arrindex = start;

    // Finché ci sono elementi in entrambi i sotto-array da confrontare
    while (leftindex < leftsize && rightindex < rightsize) {
        if (leftarr[leftindex] < rightarr[rightindex]) {
            // Se l'elemento a sinistra è minore, lo metto nell'array principale
            arr[arrindex++] = leftarr[leftindex++];
        } else {
            // Altrimenti prendo quello a destra
            arr[arrindex++] = rightarr[rightindex++];
        }
    }

    // Copio eventuali elementi rimanenti nel sotto-array sinistro
    while (leftindex < leftsize) {
        arr[arrindex++] = leftarr[leftindex++];
    }

    // Copio eventuali elementi rimanenti nel sotto-array destro
    while (rightindex < rightsize) {
        arr[arrindex++] = rightarr[rightindex++];
    }

    // Dealloco la memoria temporanea
    delete[] leftarr;
    delete[] rightarr;
}

// Funzione ricorsiva per ordinare l'array tramite MergeSort
template <typename T>
void mergesort(T* arr, const size_t& start, const size_t& end) {
    // Caso base: se la parte da ordinare ha un solo elemento o è vuota
    if (start >= end) return;

    // Calcolo dell'indice centrale
    size_t mid = (start + end) / 2;

    // Chiamata ricorsiva sulla metà sinistra
    mergesort(arr, start, mid);

    // Chiamata ricorsiva sulla metà destra
    mergesort(arr, mid + 1, end);

    // Unisco le due metà ordinate
    merge(arr, start, mid, end);
}

// Funzione di comodo per lanciare il mergesort senza dover passare start e end
template <typename T>
void mergesort(T* arr, const size_t& size) {
    mergesort(arr, 0, size - 1); // Chiama la versione completa
}

int main() {
    size_t size = 6; // Dimensione dell'array
    int arr[] = {2, 1, 4, 7, 0, 3}; // Array da ordinare

    // Ordino l'array con MergeSort
    mergesort(arr, size);

    // Stampo l'array ordinato
    for (auto k : arr) {
        cout << k << endl;
    }

    return 0; // Fine programma
}