Cos'è mergesort?

Mergesort

Il mergesort è un <a href="https://it.wikiwhat.page/kavramlar/algoritmo%20di%20ordinamento">algoritmo di ordinamento</a> di tipo divide et impera che funziona suddividendo ripetutamente una lista in sottoliste più piccole, ordinando ciascuna sottolista e quindi unendo le sottoliste ordinate per produrre una nuova lista ordinata.

Come Funziona:

1. Divide: La lista viene divisa ricorsivamente a metà finché ogni sottolista contiene un solo elemento (che è intrinsecamente ordinato).
2. Conquer (Ordina): Le sottoliste a un elemento sono considerate ordinate.
3. Merge (Fondi): Le sottoliste vengono ripetutamente unite per produrre nuove sottoliste ordinate più grandi. Questa fase è cruciale e implica confrontare gli elementi delle due sottoliste e inserirli nell'ordine corretto nella lista risultante.

Caratteristiche Importanti:

• Complessità Temporale:

  • Caso migliore: O(n log n)
  • Caso medio: O(n log n)
  • Caso peggiore: O(n log n) Il mergesort ha una complessità temporale di O(n log n) in tutti i casi, il che lo rende un <a href="https://it.wikiwhat.page/kavramlar/algoritmo%20efficiente">algoritmo efficiente</a> per ordinare grandi quantità di dati.

• Complessità Spaziale: O(n) Il mergesort richiede spazio aggiuntivo per memorizzare le sottoliste durante il processo di unione. Questo lo rende non un algoritmo in-place.

• Stabile: Sì Il mergesort è un <a href="https://it.wikiwhat.page/kavramlar/ordinamento%20stabile">ordinamento stabile</a>, il che significa che mantiene l'ordine relativo degli elementi con chiavi uguali.

• Ricorsivo: Tipicamente implementato usando la ricorsione, sebbene sia possibile un'implementazione iterativa.

• Adatto per:

  • Ordinare liste collegate.
  • Ordinare grandi quantità di dati memorizzati su disco (ordinamento esterno).

Vantaggi:

• Prestazioni prevedibili (O(n log n) in tutti i casi).
• Stabile.
• Adatto per ordinare liste collegate.

Svantaggi:

• Richiede spazio aggiuntivo (non in-place).
• La ricorsione può aggiungere un overhead, specialmente per liste più piccole.

Esempio (Pseudocodice):

function mergesort(lista)
  if lunghezza(lista) <= 1
    return lista  // Già ordinata

  metà = lunghezza(lista) / 2
  sinistra = mergesort(lista[0..metà-1])
  destra = mergesort(lista[metà..lunghezza(lista)-1])

  return merge(sinistra, destra)

function merge(sinistra, destra)
  risultato = lista vuota
  i = 0  // Indice per sinistra
  j = 0  // Indice per destra

  while i < lunghezza(sinistra) e j < lunghezza(destra)
    se sinistra[i] <= destra[j]
      aggiungi sinistra[i] a risultato
      i = i + 1
    altrimenti
      aggiungi destra[j] a risultato
      j = j + 1

  // Aggiungi gli elementi rimanenti, se presenti
  while i < lunghezza(sinistra)
    aggiungi sinistra[i] a risultato
    i = i + 1
  while j < lunghezza(destra)
    aggiungi destra[j] a risultato
    j = j + 1

  return risultato