mastorna.it
EN

Algoritmi di ordinamento · 2/7

Merge sort

Divide l’array, ordina le metà e le fonde linearmente.

Tempo medioΘ(n log n) MemoriaΘ(n) StabileSì In placeNo

Come funziona

La ricorsione divide fino a sottosequenze di un elemento. La fusione confronta le teste di due metà già ordinate e copia ogni volta la più piccola in un buffer.

Invariante: Durante merge, il buffer contiene i più piccoli elementi già esaminati, in ordine; le due code residue restano ordinate.

Simulazione passo passo

La vista a barre mostra confronti e copie; l’albero parallelo segue le suddivisioni dell’array e le successive fusioni.

Da 2 a 16 valori. Per questo simulatore sono ammessi valori da 0 a 999.

Albero di divisione e fusione Blu: operazione corrente · verde: fusione completata

Confronti
0
Scritture
0
Scambi
0
Passaggio / livello
0
attivo confronto pivot / chiave definitivo

Pseudocodice collegato alla simulazione

Merge sort

  1. mergeSort(A, left, right)
  2. if left ≥ right: return
  3. mid ← ⌊(left + right) / 2⌋
  4. mergeSort(A, left, mid)
  5. mergeSort(A, mid + 1, right)
  6. merge(A, left, mid, right)

Merge

  1. merge(A, left, mid, right)
  2. L ← A[left … mid]
  3. R ← A[mid + 1 … right]
  4. i ← 0; j ← 0; B ← empty array
  5. while i < length(L) and j < length(R)
  6. if L[i] ≤ R[j]
  7. append L[i] to B; i ← i + 1
  8. else
  9. append R[j] to B; j ← j + 1
  10. append the remaining elements of L or R to B
  11. for k ← 0 to length(B) − 1
  12. A[left + k] ← B[k]

La riga evidenziata corrisponde all’operazione descritta nel simulatore. I dettagli di gestione degli indici sono intenzionalmente semplificati.

Studio della complessità

Caso miglioreΘ(n log n)

Anche un input ordinato attraversa log n livelli e ogni livello fonde complessivamente n elementi: Θ(n log n).

Caso medioΘ(n log n)

La forma dell’albero non dipende dall’ordine dei valori: T(n)=2T(n/2)+Θ(n)=Θ(n log n).

Caso peggioreΘ(n log n)

Gli stessi log n livelli e lo stesso lavoro lineare per livello danno una garanzia Θ(n log n).

Spazio ausiliarioΘ(n)

La versione classica per array usa un buffer Θ(n) e uno stack Θ(log n). È stabile scegliendo dalla metà sinistra in caso di parità.

Proprietà in breve

Stabile

La stabilità riguarda l’ordine relativo degli elementi con chiave uguale.

Non in place

La classificazione considera la versione dell’algoritmo mostrata in questa pagina.

Quando usarlo e che cosa evitare

Buona scelta quando…

Scelta solida quando servono stabilità e garanzia, per liste collegate e per ordinamento esterno di dati che non entrano in memoria.

Errore comune

Una fusione che sceglie dalla metà destra sulle chiavi uguali rende l’algoritmo non stabile.