Merge sort in Python
Merge sort divide ricorsivamente e fonde sottoliste ordinate.
Che cos’è Merge sort?
Merge sort divide ricorsivamente e fonde sottoliste ordinate.
Ordina con la strategia divide et impera.
Quando si usa?
- Comprendere algoritmi e strutture dati.
- Osservare ogni passaggio e gestire i casi limite.
- Confrontare tempo di esecuzione e memoria.
Visualizzatore di Merge sort in Python
O(n log n)Usa Avvia o Passo per seguire ogni confronto e spostamento dei dati.
Codice di esempio
main.py
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))Output previsto
[3, 9, 10, 27, 38, 43, 82]Come funziona
Garantisce tempo O(n log n) e richiede O(n) memoria aggiuntiva.
Modifica i valori ed esegui il programma nel compilatore Python online CodeUtility senza installare Python.
Esercizi pratici
Modifica gli input e verifica i casi limite prima di usare dataset più grandi.
- Prova input vuoto, un elemento e duplicati.
- Stampa lo stato dopo ogni passaggio.
- Confronta le prestazioni con un’altra soluzione.