Problema con algoritmo merge sort

[ZfreS]

Io ti ringrazio tantissimo per l'impegno che stai facendo per farmi capire, ma mi sfugge sempre un pezzo, cerco di esprimermi meglio. La funzione merge prende le due partizioni da un solo elemnto, come fà a ricavarne una ordinata? Poi ho capito che procede a ritroso fino ad arrivare un'unico array ordinato, ma il mio dubbio sta proprio alla base del primo array che prende la merge.

[Super Squirrel]

Immagina di avere il seguente main

Codice:

int main()
{
    int v[] = {2, 1};
    stampa_array(v, 2);
    merge_sort(v, 0, 1);
    stampa_array(v, 2);
}

e prova a seguire passo passo quello che avviene una volta richiamata la funzione merge_sort().

In ogni caso secondo me il problema consiste nel fatto che tu non abbia capito come funzioni e cosa faccia la funzione merge().
Per esempio come diventerà il vettore
v = 3 5 2 0 1 7 9 2 6 8 3 2
dopo aver richiamato la funzione merge(v, 3, 6, 9)?

[ZfreS]

Se chiamo la funzione merge sul vettore scritto da te il valore di s = 3 d non puo essere 9 ma 2 e c dovrebbe essere o 92 visto che è metà del vettore, o sbaglio? Nel main ch hai scritto tu il vettore 2 1 viene diviso in due vettori con le due funzioni ricorsive di per se ordinati, ma poi entra in gioco la merge e in effetti non capisco sa faccia esattamente. Potresti speigarmelo proprio su questo esempio semplice?

[Super Squirrel]

Se chiamo la funzione merge sul vettore scritto da te il valore di s = 3 d non puo essere 9 ma 2 e c dovrebbe essere o 92 visto che è metà del vettore

La funzione merge() si aspetta semplicemente due partizioni ordinate, dove la prima partizione inizia dall'indice s e termina all'indice c, mentre la seconda partizione inizia dall'indice c+1 e termina all'indice d.
Considerando il vettore
v = 3 5 2 0 1 7 9 2 6 8 3 2
con la chiamata a funzione merge(v, 3, 6, 9), le due partizioni da unire sono le seguenti:
3 5 2 0 1 7 9 2 6 8 3 2
la funzione in pratica riempie un array (di dimensione pari alla somma degli elementi delle 2 partizioni) prendendo di volta in volta il minimo tra l'elemento corrente (che parte dal primo) delle due partizioni. Tale vettore viene poi sostituito alle 2 partizioni. Quindi all'uscita dalla funzione sarà
v = 3 5 2 0 1 2 6 7 8 9 3 2

[ZfreS]

Ah perfetto, adesso ho capito, quando mi hai dato i valori da considerare, pensavo che ti riferissi ai numeri e non agli indici dell'array. Ti ringrazio tantissimo per la pazienza che hai avuto nello spiegare e sopratutto la chiarezza. Buona serata!

[Super Squirrel]

Non ho capito bene quale sia stato il misunderstanding, in ogni caso di niente!