Merge sort e ricorsione

di Anonimizzato3626 il
1 risposte
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

  • Se leggi bene, viene passato proprio l'array 'a' .
Devi accedere o registrarti per scrivere nel forum
1 risposte