Guida pratica al merge sort (con balletto)

Ciao, oggi vedremo assieme una spiegazione approfondita e chiara del Merge Sort, accompagnata alla fine da un video esplicativo — incluso uno con un “balletto” animato che segue i passi dell’algoritmo.

Il merge sort è un algoritmo di ordinamento efficiente che utilizza un approccio “divide et impera“. Divide ricorsivamente l’array da ordinare in sottoarray più piccoli, ordina questi sottoarray e infine combina (fonde) i risultati ordinati per ottenere l’array completamente ordinato. La sua complessità temporale è O(n log n), rendendolo ideale per ordinare grandi quantità di dati.

In sintesi

• Merge Sort: algoritmo robusto, stabile, efficiente e prevedibile.
• Strategia: dividere‑ordinare‑unire.
• Complessità: sempre O(n log n), con spazio extra.
• Ottimo per scenari dove la stabilità conta o i dati sono molto grandi o su disco.

Merge Sort: Dividi per conquistare (cioè?)

1. Idea chiave

Merge Sort è un algoritmo ricorsivo che utilizza la strategia divide et impera:

1. Se la lista ha 0 o 1 elemento, è già ordinata.
2. Altrimenti, dividi la lista in due metà.
3. Ordina ciascuna metà in modo ricorsivo.
4. Unisci (merge) le due metà ordinate in una lista unica, mantenendo l’ordine.

È stabile (rispetta l’ordine relativo di elementi uguali), e garantisce complessità O(n log n) nel caso medio e peggiore, con spazio ausiliario O(n).

2. Funzionamento passo-passo

Supponiamo di dover ordinare:

[10, 3, 15, 2, 1, 4, 9, 0]

a. Divisione ricorsiva

• Primo livello:
  • sinistra → [10, 3, 15, 2]
  • destra → [1, 4, 9, 0]
• E così via, fino a ottenere liste di 1 elemento:
  • [10], [3], [15], …

b. Fusione ordinata (merge)

• Si fondono coppie:
  • [10] + [3] → [3, 10]
  • [15] + [2] → [2, 15]
• Poi:
  • [3, 10] + [2, 15] → [2, 3, 10, 15]
• Stessa cosa per l’altra metà…
• Infine:
  • [2, 3, 10, 15] + [0, 1, 4, 9] → [0, 1, 2, 3, 4, 9, 10, 15] (it.wikipedia.org, en.wikipedia.org).

3. Pseudocodice (Top‑Down)

function merge_sort(A):
  if len(A) ≤ 1:
    return A
  mid = len(A)//2
  left = merge_sort(A[:mid])
  right = merge_sort(A[mid:])
  return merge(left, right)

function merge(L, R):
  result = []
  while L and R:
    if L[0] ≤ R[0]:
      result.append(L.pop(0))
    else:
      result.append(R.pop(0))
  result += L + R
  return result

Complessità:

• Tempo: T(n) = 2 T(n/2) + Θ(n) → Θ(n log n)
• Spazio: O(n) (lo spazio per le fusioni)

4. Quando usarlo?

• Stabile: mantiene l’ordine degli elementi duplicati.
• Prevedibile: nessun caro caso peggiore, sempre O(n log n).
• Ideale per:
  • strutture a accesso sequenziale (es. liste collegate)
  • merge esterni su dati giganteschi su disco
• Contro: richiede memoria aggiuntiva (array ausiliari).

# Python program for implementation of MergeSort


def mergeSort(arr):
	if len(arr) > 1:

		# Finding the mid of the array
		mid = len(arr)//2

		# Dividing the array elements
		L = arr[:mid]

		# Into 2 halves
		R = arr[mid:]

		# Sorting the first half
		mergeSort(L)

		# Sorting the second half
		mergeSort(R)

		i = j = k = 0

		# Copy data to temp arrays L[] and R[]
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		# Checking if any element was left
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1


# Code to print the list
def printList(arr):
	for i in range(len(arr)):
		print(arr[i], end=" ")
	print()


# Driver Code
if __name__ == '__main__':
	arr = [12, 11, 13, 5, 6, 7]
	print("Given array is")
	printList(arr)
	mergeSort(arr)
	print("\nSorted array is ")
	printList(arr)

# This code is contributed by Mayank Khanna
# source: https://www.geeksforgeeks.org/merge-sort/

(fonte)