Merge sort: dividere, ordinare, unire
Implementi merge sort ricorsivamente, tracci l'albero divide-and-conquer e spieghi perché garantisce O(n log n) in ogni caso
Merge sort: dividere, ordinare, unire è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 2 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
Intuizione del divide et impera
Merge sort è un classico algoritmo divide et impera: divide l'array a metà, ordina ricorsivamente ciascuna metà, quindi unisce le due metà ordinate in un unico risultato ordinato. L'idea è che unire due array ordinati richiede O(n), un costo molto inferiore rispetto all'ordinamento da zero. Questa scomposizione produce un albero di ricorsione con log n livelli, ognuno dei quali richiede O(n) per l'unione, ottenendo il limite ottimale per gli algoritmi di ordinamento basati su confronti, pari a O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Spiegazione del passaggio di unione
Per unire due array ordinati, si mantengono due puntatori, uno per ciascuna metà. Si confrontano gli elementi iniziali, si copia quello più piccolo nell'output e si avanza il puntatore corrispondente. Quando una metà è esaurita, si copia direttamente il resto dell'altra. Questa operazione richiede O(n) tempo e O(n) spazio per l'array di output. Il passaggio di unione è il cuore algoritmico di merge sort: lo comprenda a fondo.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Implementazione completa del merge sort
Unendo divisione e fusione: le chiamate ricorsive dimezzano il problema fino a lasciare solo elementi singoli (ordinati in modo banale), poi le chiamate di fusione li ricombinano. A ogni livello dell'albero di ricorsione vengono fusi complessivamente gli stessi n elementi (distribuiti tra più fusioni). La profondità della ricorsione è log₂(n), per un tempo totale O(n log n) e uno spazio ausiliario O(n) per gli array di output della fusione, oltre a una profondità dello stack delle chiamate di O(log n).
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Albero di ricorsione del merge sort
Consideri l'albero di ricorsione del merge sort per n=8: il livello 0 contiene un array di 8 elementi; il livello 1 contiene due array da 4; il livello 2 quattro array da 2; il livello 3 otto elementi singoli (casi base). Risalendo, dal livello 3→2 vengono fusi complessivamente 8 elementi, dal livello 2→1 altri 8, e dal livello 1→0 altri 8. Sono 3 livelli × 8 elementi = 24 operazioni ≈ 8 × log₂(8) = 24. Questo conferma O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Merge sort in-place
Il merge sort ricorsivo standard alloca spazio ausiliario O(n) per l'output della fusione. Esiste un merge sort in-place, ma è complesso e presenta fattori costanti elevati: raramente viene richiesto nei colloqui. La domanda di approfondimento più comune nei colloqui è: 'È possibile eseguire il merge sort con spazio aggiuntivo O(1)?' La risposta corretta è: 'In teoria sì, ma le implementazioni pratiche rinunciano allo spazio O(n) oppure aggiungono complessità; Timsort di Python usa spazio O(n) per la fusione.'
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Il merge sort è stabile
Il merge sort è stabile: nell'output fuso, gli elementi uguali della metà sinistra compaiono sempre prima di quelli della metà destra. Questo è garantito dall'uso di <= (e non di <) quando si dà la precedenza all'elemento a sinistra. La stabilità è importante per l'ordinamento su più chiavi. Le funzioni integrate di Python sorted() e list.sort() usano Timsort, anch'esso stabile e O(n log n), il che le rende la scelta sicura per tutto il codice di produzione.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Fusione di k array ordinati
Fondere k array ordinati con n elementi complessivi si può fare fondendo ripetutamente le coppie (come in un tabellone a eliminazione), in tempo O(n log k). Ogni livello di fusione elabora n elementi e ci sono log k livelli. In alternativa, si può usare un min-heap di dimensione k: si inserisce il più piccolo elemento ancora disponibile di ogni array, si estrae il minimo e si inserisce l'elemento successivo di quell'array. Anche l'approccio con heap è O(n log k), ma usa meno memoria quando k è molto grande.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Contare le inversioni con il merge sort
Contare le inversioni (coppie per cui a[i] > a[j] e i < j) in O(n log n) richiede una versione modificata del merge sort. Durante il passaggio di fusione, quando un elemento del sottoarray destro è minore di un elemento del sottoarray sinistro, forma un'inversione con ogni elemento ancora rimanente nel sottoarray sinistro. In quel momento, si aggiunge len(left) - i al conteggio.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Merge sort e quick sort a confronto
Il merge sort garantisce O(n log n) in tutti i casi, è stabile ed è la scelta migliore per le liste concatenate e l'ordinamento esterno. Il quick sort ha un caso medio O(n log n) ma un caso peggiore O(n²), è in-place (con spazio dello stack O(log n)) e spesso è più veloce nella pratica grazie all'efficienza della cache sugli array. L'ordinamento integrato di Python usa Timsort (una variante del merge sort): è sempre la scelta predefinita corretta.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Ordinamento esterno: merge sort su larga scala
Il merge sort è l'algoritmo alla base dell'ordinamento esterno (per ordinare dati troppo grandi per entrare nella RAM). I dati vengono letti a blocchi, ogni blocco viene ordinato in memoria e i blocchi vengono fusi dal disco. Il passaggio di fusione legge un elemento alla volta da ciascuna sequenza ordinata, mantenendo contemporaneamente in memoria solo O(k) elementi (uno per sequenza). Per questo il merge sort viene usato nei database, in Hadoop MapReduce e nei classici algoritmi di ordinamento su nastro.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Riepilogo del merge sort e suggerimenti per il colloquio
Nei colloqui, implementare il merge sort in modo chiaro dimostra la comprensione della ricorsione, del passaggio di fusione e della tecnica divide et impera. Domande di approfondimento comuni:
- Perché O(n log n) e non O(n²)? (log n livelli × n operazioni per livello)
- È stabile? (Sì, si usa <= nella fusione)
- Quanto spazio richiede? (O(n) ausiliario + stack O(log n))
- È possibile farlo in modo iterativo? (Sì, con il merge sort bottom-up)
- Come lo si applicherebbe a una lista concatenata? (È più semplice che su un array: nessun costo di slice O(n); si usano due puntatori, uno lento e uno veloce, per trovare il punto centrale)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Verifica rapida
Metta alla prova la sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato: il merge sort divide l'array nel punto centrale, ordina ricorsivamente ciascuna metà e fonde le due metà ordinate in O(n), ottenendo un tempo di esecuzione totale O(n log n) su log n livelli di ricorsione, il passaggio di fusione usa <= per scegliere l'elemento a sinistra in caso di parità, garantendo la stabilità e il merge sort è l'algoritmo preferibile per le liste concatenate, l'ordinamento esterno e i casi in cui è richiesta la stabilità, mentre il quick sort è preferibile per gli array in memoria quando lo spazio è limitato. Ora implementeremo il quick sort ed esploreremo le strategie di selezione del pivot.
Domande Frequenti
La lezione «Merge sort: dividere, ordinare, unire» è gratuita?
Sì — il testo completo di «Merge sort: dividere, ordinare, unire» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Merge sort: dividere, ordinare, unire»?
Implementi merge sort ricorsivamente, tracci l'albero divide-and-conquer e spieghi perché garantisce O(n log n) in ogni caso Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 2 di 4.
Quanto tempo richiede la lezione «Merge sort: dividere, ordinare, unire»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Bubble sort e insertion sort
- Merge sort: dividere, ordinare, unire
- Quick sort e selezione del pivot
- Ordinamenti non basati sui confronti e sort() di Python