Merge sort e ricorsione

di il
1 risposte

Merge sort e ricorsione

Salve a tutti,
spero di aver postato nella giusta sezione. Ho un porblema con la ricorsione in genere ed il mergesort in particolare, sul concetto generale ci sono, ho capito che l'algoritmo divide l'array fino al singolo elemento ma non capisco come fa poi il merge, perchè mi perdo tra le chiamate ricorsive; stò usando il seguente pseudocodice:
merge (a[], left, center, right)  
    i ? left
    j ? center + 1
    k ? 0
 
    while ((i <= center) && (j <= right)) do
       if (a[i] <= a[j])
        then
          b[k] ? a[i]
          i ? i + 1
        else
           b[k] ? a[j]
           j ? j + 1  
           k ? k + 1
    end while
 
    while (i <= center) do
          b[k] ? a[i]
          i ? i + 1
          k ? k + 1
    end while
 
    while (j <= right) do
          b[k] ? a[j] 
          j ? j + 1
          k ? k + 1
    end while
 
    for k ? left to right do
        a[k] ? b[k - left]
 
 mergesort (a[], left, right)
    if (left < right) then
        center ? (left + right) / 2
        mergesort(a, left, center)
        mergesort(a, center+1, right)
        merge(a, left, center, right)
non mi è chiaro quando viene effettuata la prima chiamata a merge qual'è l'array che viene passato.
grazie per la disponibilità
buona serata

1 Risposte

Devi accedere o registrarti per scrivere nel forum
1 risposte