Problema con algoritmo merge sort

Ho trovato un'implmentazione del merge sort, ma eseguendo il codice il programma va in crash:

Funzione mergesort:

Codice:

void mergeSort(int arr[], int s, int d)
{
   if (s < d)
   {
      int c =  (d - s) / 2;
         mergeSort(arr, s, c);
         mergeSort(arr, c + 1, d);
         merge(arr, s, c, d);
   }
   
}



Funzione merge:

Codice:

void merge(int arr[], int s, int c, int d)
{
      int* aux = new int[d + 1];
      int i, j;

      for (i = c + 1; i > s; i--)
         aux[i - 1] = arr[i - 1];
      for (j = c; j < d; j++)
         aux[d + c - j] = arr[j + 1];
      for (int k = s; k <= d; k++)
         if (aux[j] < aux[i])
            arr[k] = aux[j--];
         else
            arr[k] = aux[i++];
      delete[] aux;
}



Esecuzione nel main:

Codice:

int a[] = { 10, 3, 15, 2, 1, 4, 9, 0 };
   cout << "Ecco l'array disordinato: " << endl;
   stampaArray(a, 8);
   cout << "Ecco l'array ordinato: " << endl;
   mergeSort(a, 0, 7);
   stampaArray(a, 8);


E poi non o capito due cose:
1) Nel primo blocco di codice non ho capito quando viene eseguita la funzione ricorsiva

Codice:

mergeSort(arr, c + 1, d);

2) Non ho capito cosa fa il codice del secondo blocco dal primo ciclo for fino al delete.
Potreste aiutarmi a capire la causa del crash e spiegarmi le cose che non ho capito? Grazie in anticipo!

Cosa significa "ho trovato"? In generale sai come funziona il merge-sort?

In ogni caso il crash è dovuto alla funzione mergeSort(). Se entriamo nella funzione con s=0 e d=3 tutto OK, ipotizziamo invece di entrare nella funzione con s=4 e d=7, ci aspettiamo le partizioni 4-5 e 6-7, ma la funzione restituisce 4-1 e 2-7... c'è evidentemente qualcosa che non va. Rifletti sul valore di "c".

Per quanto riguarda la funzione merge() ho capito cosa fa e sembra essere funzionante. Per esempio ipotizziamo di passargli s=0, d=6, c=3 e
arr={1, 3, 7, 8, 0, 2, 5}
al termine dei primi due cicli for sarà i=s, j=d e
aux={1, 3, 7, 8, 5, 2, 0}
in pratica la seconda sottosequenza viene messa in ordine inverso.
Detto questo credo che l'ultimo for sia semplice da capire.
Lo scopo di tutto ciò dovrebbe essere quello di evitare di considerare le due sottosequenze separatamente stando lì a controllare ogni volta se una delle due sottosequenze è "vuota"
Nel seguente codice ti mostro quella che potrebbe essere la strategia "classica":

Codice:

void merge_(int *v, const unsigned int s, const unsigned int c, const unsigned int d)
{
    unsigned int dim = d - s + 1;
    int *u = new int[dim];
    unsigned int i;
    unsigned int i_s = s;
    unsigned int i_d = c + 1;
    for(i = 0; i < dim; ++i)
    {
        if(i_s <= c)
        {
            if(i_d <= d)
            {
                if(v[i_s] < v[i_d])
                {
                    u[i] = v[i_s++];
                }
                else
                {
                    u[i] = v[i_d++];
                }
            }
            else
            {
                u[i] = v[i_s++];
            }
        }
        else
        {
            u[i] = v[i_d++];
        }
    }
    for(i = 0; i < dim; ++i)
    {
        v[s + i] = u[i];
    }
    delete[] u;
}

Sper di essere stato chiaro, se hai qualche dubbio chiedi pure.

Allora per la funzione mergeSort se scrivo int c = (d+s)/2 funziona, però guardando in rete la soluzione più classica per l'algoritmo di fusione dei vettori, ovvero la funzione merge è:

Codice:

void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
 
    int L[n1], R[n2];
 
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
 
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 


Comunque penso che ci siano molt modi di implementarlo, ma qual'è quello più efficiente? Poi volevo togliermi un altro dubbio per quanto riguarda la funzione mergeSort: la prima funzione ricorsiva lavora su una metà dell'array spezzato, l'altra lavora sull'altra metà e questo finche non si arriva ad isolare tutti gli elementi dellarray, ma come fa la funzione di "fusione" ad ordinare il ordine crescente l'array?

però guardando in rete la soluzione più classica per l'algoritmo di fusione dei vettori, ovvero la funzione merge è:...

Questa sfrutta lo stesso ragionamento della funzione che ho postato in precedenza (attento cmq che contiene VLA).

Poi volevo togliermi un altro dubbio per quanto riguarda la funzione mergeSort: la prima funzione ricorsiva lavora su una metà dell'array spezzato, l'altra lavora sull'altra metà e questo finche non si arriva ad isolare tutti gli elementi dellarray, ma come fa la funzione di "fusione" ad ordinare il ordine crescente l'array?

Non sono sicuro di aver capito la domanda, in ogni caso prima di pensare all'efficienza dell'algoritmo utilizzato, hai capito cosa fa in generale la funzione merge()? Che caratteristica hanno le due "partizioni" dell'array che riceve la funzione?

Allora provo a spiegarmi meglio: cominciamo dalla funzione mergeSort:
la prima istruzione divide l'array a metà, la seconda istruzione è il richiamo alla funzione stessa e divide a metà la prima metà dell'array finchè non arriva ad un'unica cella indivisibile, ma di queste uniche celle ce ne sono tante. La seconda istruzione è la chiamata alla funzione stessa che però va a dividere l'altra metà dell'array finchè non rimangono tante celle separate. A quel punto viene chiamata la funzione merge ed è qui che non capisco: la funzione merge deve unire tutte le celle in un array allocato dinamicamente, ma come fà a farlo in ordine. Oppure sono le istruzioni ricorsive che hanno diviso in ordine l'array? Cos'è il VLA? Se ti riferisci al fatto che ci sono due array con indici non costanti, allora sì, me ne sono accorto

Cos'è il VLA? Se ti riferisci al fatto che ci sono due array con indici non costanti, allora sì, me ne sono accorto

VLA sta per Variable Length Array.
Si mi riferivo a quei due array, in ogni caso più che indici, si tratta di dimensioni non costanti.

Allora provo a spiegarmi meglio: cominciamo dalla funzione mergeSort:
la prima istruzione divide l'array a metà, la seconda istruzione è il richiamo alla funzione stessa e divide a metà la prima metà dell'array finchè non arriva ad un'unica cella indivisibile, ma di queste uniche celle ce ne sono tante. La seconda istruzione è la chiamata alla funzione stessa che però va a dividere l'altra metà dell'array finchè non rimangono tante celle separate. A quel punto viene chiamata la funzione merge ed è qui che non capisco: la funzione merge deve unire tutte le celle in un array allocato dinamicamente, ma come fà a farlo in ordine. Oppure sono le istruzioni ricorsive che hanno diviso in ordine l'array?

Le frecce in blu indicano la divisione dell'array in 2 partizioni, mentre quelle in arancione sono relative al merge.
Ho chiarito il tuo dubbio o intendevi altro?

Si, questo schema di funzionamento lo conoscevo e l'avevo già capito, però il mio dubbio satav in un altra cosa: segui nell'immagine la divisione del vettore di sinistra:7 6 5 4 poi continua a sinistra in: 7 6 poi sempre a sinistra 7. Ecco ora abbiamo due caselle separate: il 7 e il 6, come fa la funzione che li unisce a prenderli correttamente in ordine crescente?

Ecco ora abbiamo due caselle separate: il 7 e il 6, come fa la funzione che li unisce a prenderli correttamente in ordine crescente?

L'array a quel punto è
7 6 5 4 3 2 1
dopo la chiamata a funzione merge() con s=0, c=0 e d=1, l'array diventa
6 7 5 4 3 2 1

In pratica la funzione merge() si aspetta due partizioni ordinate e una partizione di un solo elemento risulta ovviamente ordinata.

In ogni caso continuo a non capire quale sia il tuo dubbio... ripeto la domanda fatta nel precedente post: hai capito cosa fa e come funziona la funzione merge()?

In pratica la funzione merge() si aspetta due partizioni ordinate

Ecco proprio questo non capisco: la funzione merge prende le parti già ordinate, ma chi è che le ordina? La funzione mergesort serve a dividere tutto l'array, la merge a ricomporlo, ma chi è che ordina una volta che è tutto diviso?
Non ho capito questo: dopo la chiamata a funzione merge() con s=0, c=0 e d=1, l'array diventa
6 7 5 4 3 2 1
Non è che hai frainteso il significato delle variabili? s sta per sinistra ovvero il primo elemento dell'array, c sta per centro a indicare la meta dell'array e d sta per destra a indicare l'ultimo elemento dell'array.

la funzione merge prende le parti già ordinate, ma chi è che le ordina?

Ovviamente la stessa funzione merge() che da 2 partizioni di un solo elemento (che risultano già ordinate) ricava una partizione ordinata di 2 elementi e così via (seguendo un procedimento a ritroso imposto dalla ricorsione).

Non è che hai frainteso il significato delle variabili? s sta per sinistra ovvero il primo elemento dell'array, c sta per centro a indicare la meta dell'array e d sta per destra a indicare l'ultimo elemento dell'array.

Ho inteso che considerata una generica partizione (e non l'intero array), s rappresenta l'indice del primo elemento, d l'indice dell'ultimo elemento e c l'indice dell'elemento centrale. Quindi la partizione s;d viene a sua volta divisa nelle partizioni s;c e c+1;d.
Detto questo cosa non ti convince della seguente affermazione:

dopo la chiamata a funzione merge() con s=0, c=0 e d=1, l'array diventa
6 7 5 4 3 2 1

che ti ha fatto pensare che io abbia frainteso il significato delle variabili?

Se ti può essere utile ti posto un'altra immagine in cui ho anche evidenziato l'ordine in cui vengono richiamate le funzioni merge_sort() e merge():