Merge sort
Ultimo aggiornamento
Il merge sort è un algoritmo divide et impera. Divide ricorsivamente l'array a metà finché ogni pezzo non ha un solo elemento (che è ordinato per definizione), poi fonde di nuovo i pezzi in ordine. Il passo di fusione scorre due sottoarray ordinati con due puntatori, copiando ogni volta il più piccolo dei due elementi in testa. Premi play qui sopra per vedere l'array ricostruito fusione dopo fusione.
Dato che divide sempre a metà, il merge sort richiede tempo O(n log n) in ogni caso: il suo caso peggiore è buono quanto il migliore. Il compromesso è O(n) di spazio extra per il buffer temporaneo della fusione.
Complessità temporale e spaziale
| Caso | Complessità | Note |
|---|---|---|
| Caso migliore | O(n log n) | Divide sempre a metà l'input |
| Caso medio | O(n log n) | Ordine casuale |
| Caso peggiore | O(n log n) | Garantito: nessun input sfavorevole |
| Spazio | O(n) | Buffer temporaneo per la fusione |
| Stabile | Sì | I pareggi si risolvono prendendo prima da sinistra durante la fusione |
Passo dopo passo
| Passo | Cosa succede |
|---|---|
| 1 | Se l'intervallo ha 0 o 1 elementi, è già ordinato. |
| 2 | Dividi l'intervallo in due metà. |
| 3 | Applica ricorsivamente il merge sort alla metà sinistra. |
| 4 | Applica ricorsivamente il merge sort alla metà destra. |
| 5 | Fondi le due metà ordinate con due puntatori. |
Esempio svolto
Ordinamento di [5, 2, 4, 1]:
| Passata | Array | Azione |
|---|---|---|
| Divisione | [5, 2] | [4, 1] | Dividi l'array in due metà |
| Divisione | [5] [2] | [4] [1] | Dividi ancora finché ogni pezzo è un solo elemento |
| Fusione | [2, 5] | [1, 4] | Fondi [5],[2] in [2, 5] e [4],[1] in [1, 4] |
| Fusione | [1, 2, 4, 5] | Fondi [2, 5] e [1, 4]: prendi 1, poi 2, poi 4, poi 5 |
| Fine | [1, 2, 4, 5] | L'array è completamente ordinato |
Quando usare il merge sort
| Usalo quando | Evitalo quando |
|---|---|
Ti serve un caso peggiore O(n log n) garantito | La memoria è poca e O(n) di spazio extra non è accettabile |
| Conta la stabilità (le chiavi uguali mantengono il loro ordine) | Ordini array piccoli, dove l'insertion sort è più veloce |
| Stai ordinando una lista concatenata | L'ordinamento in loco è un requisito irrinunciabile |
| I dati sono troppo grandi per la RAM (ordinamento esterno) | La località della cache domina e vincono le passate in loco del quicksort |
Codice Merge Sort
Un'implementazione di Merge Sort pulita ed eseguibile in Python, JavaScript, Java, C++, C, Pseudocode. Scegli un linguaggio, copia il codice o aprilo già caricato nel Playground di Coddy.
Codice Merge Sort in Python
Python
1def merge_sort(a):2 if len(a) <= 1:3 return a4 mid = len(a) // 25 left = merge_sort(a[:mid])6 right = merge_sort(a[mid:])7 return merge(left, right)8
9
10def merge(left, right):11 out = []12 i = j = 013 while i < len(left) and j < len(right):14 if left[i] <= right[j]:15 out.append(left[i])16 i += 117 else:18 out.append(right[j])19 j += 120 out.extend(left[i:])21 out.extend(right[j:])22 return out23
24
25nums = [38, 27, 43, 3, 9, 82, 10]26print("Before:", nums)27print("After: ", merge_sort(nums))Codice Merge Sort in JavaScript
JavaScript
1function mergeSort(arr) {2 if (arr.length <= 1) return arr;3 const mid = Math.floor(arr.length / 2);4 const left = mergeSort(arr.slice(0, mid));5 const right = mergeSort(arr.slice(mid));6 return merge(left, right);7}8
9// Merge two sorted arrays into one sorted array10function merge(left, right) {11 const out = [];12 let i = 0;13 let j = 0;14 while (i < left.length && j < right.length) {15 out.push(left[i] <= right[j] ? left[i++] : right[j++]);16 }17 return out.concat(left.slice(i), right.slice(j));18}19
20const data = [5, 2, 9, 1, 7, 3];21console.log("Before:", data);22console.log("Sorted:", mergeSort(data));Codice Merge Sort in Java
Java
1import java.util.Arrays;2
3public class Main {4 static void mergeSort(int[] arr, int left, int right) {5 if (left >= right) return;6 int mid = (left + right) / 2;7 mergeSort(arr, left, mid);8 mergeSort(arr, mid + 1, right);9 merge(arr, left, mid, right);10 }11
12 // Merge two sorted halves into a temp array, then copy back13 static void merge(int[] arr, int left, int mid, int right) {14 int[] tmp = new int[right - left + 1];15 int i = left, j = mid + 1, k = 0;16 while (i <= mid && j <= right) {17 tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];18 }19 while (i <= mid) tmp[k++] = arr[i++];20 while (j <= right) tmp[k++] = arr[j++];21 System.arraycopy(tmp, 0, arr, left, tmp.length);22 }23
24 public static void main(String[] args) {25 int[] arr = {38, 27, 43, 3, 9, 82, 10};26 System.out.println("Before: " + Arrays.toString(arr));27 mergeSort(arr, 0, arr.length - 1);28 System.out.println("After: " + Arrays.toString(arr));29 }30}Codice Merge Sort in C++
C++
1#include <iostream>2#include <vector>3
4void printVec(const std::vector<int>& a) {5 for (int x : a) std::cout << x << " ";6 std::cout << "\n";7}8
9void merge(std::vector<int>& a, int lo, int mid, int hi) {10 std::vector<int> tmp;11 tmp.reserve(hi - lo + 1);12 int i = lo, j = mid + 1;13 while (i <= mid && j <= hi) {14 if (a[i] <= a[j]) tmp.push_back(a[i++]);15 else tmp.push_back(a[j++]);16 }17 while (i <= mid) tmp.push_back(a[i++]);18 while (j <= hi) tmp.push_back(a[j++]);19 for (size_t k = 0; k < tmp.size(); ++k) a[lo + k] = tmp[k];20}21
22void mergeSort(std::vector<int>& a, int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main() {31 std::vector<int> data = {38, 27, 43, 3, 9, 82, 10};32 std::cout << "Before: ";33 printVec(data);34 mergeSort(data, 0, static_cast<int>(data.size()) - 1);35 std::cout << "After: ";36 printVec(data);37 return 0;38}Codice Merge Sort in C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void merge(int a[], int lo, int mid, int hi) {10 int* tmp = malloc((hi - lo + 1) * sizeof(int));11 int i = lo, j = mid + 1, k = 0;12 while (i <= mid && j <= hi) {13 if (a[i] <= a[j]) tmp[k++] = a[i++];14 else tmp[k++] = a[j++];15 }16 while (i <= mid) tmp[k++] = a[i++];17 while (j <= hi) tmp[k++] = a[j++];18 for (k = 0; k <= hi - lo; k++) a[lo + k] = tmp[k];19 free(tmp);20}21
22void mergeSort(int a[], int lo, int hi) {23 if (lo >= hi) return;24 int mid = lo + (hi - lo) / 2;25 mergeSort(a, lo, mid); // sort the left half26 mergeSort(a, mid + 1, hi); // sort the right half27 merge(a, lo, mid, hi); // merge the sorted halves28}29
30int main(void) {31 int data[] = {38, 27, 43, 3, 9, 82, 10};32 int n = sizeof(data) / sizeof(data[0]);33 printf("Before: ");34 printArr(data, n);35 mergeSort(data, 0, n - 1);36 printf("After: ");37 printArr(data, n);38 return 0;39}Codice Merge Sort in Pseudocode
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74nums[1] ← 75nums[2] ← 36nums[3] ← 97nums[4] ← 18nums[5] ← 59nums[6] ← 810nums[7] ← 211DECLARE temp : ARRAY[1:7] OF INTEGER12DECLARE i : INTEGER13
14PROCEDURE merge(lo : INTEGER, mid : INTEGER, hi : INTEGER)15 DECLARE a : INTEGER16 DECLARE b : INTEGER17 DECLARE k : INTEGER18 a ← lo19 b ← mid + 120 k ← lo21 WHILE a <= mid AND b <= hi DO22 IF nums[a] <= nums[b] THEN23 temp[k] ← nums[a]24 a ← a + 125 ELSE26 temp[k] ← nums[b]27 b ← b + 128 ENDIF29 k ← k + 130 ENDWHILE31 WHILE a <= mid DO32 temp[k] ← nums[a]33 a ← a + 134 k ← k + 135 ENDWHILE36 WHILE b <= hi DO37 temp[k] ← nums[b]38 b ← b + 139 k ← k + 140 ENDWHILE41 FOR k ← lo TO hi42 nums[k] ← temp[k]43 NEXT k44ENDPROCEDURE45
46PROCEDURE mergeSort(lo : INTEGER, hi : INTEGER)47 DECLARE mid : INTEGER48 IF lo < hi THEN49 mid ← (lo + hi) DIV 250 // Sort each half, then merge them51 CALL mergeSort(lo, mid)52 CALL mergeSort(mid + 1, hi)53 CALL merge(lo, mid, hi)54 ENDIF55ENDPROCEDURE56
57CALL mergeSort(1, n)58
59FOR i ← 1 TO n60 OUTPUT nums[i]61NEXT iDomande frequenti sul merge sort
Qual è la complessità temporale del merge sort?
Il merge sort è
O(n log n) nel caso migliore, medio e peggiore, perché divide sempre l'array a metà. Usa O(n) di spazio extra per il buffer di fusione.Il merge sort è stabile?
Sì, se il passo di fusione risolve i pareggi prendendo prima dalla metà sinistra. Così gli elementi uguali mantengono il loro ordine relativo originale, ed è per questo che il merge sort è una scelta comune per l'ordinamento stabile.
Perché usare il merge sort invece del quicksort?
Il merge sort garantisce
O(n log n) anche con input ostili ed è stabile, mentre il quicksort può degradare a O(n²). Il merge sort è anche preferito per le liste concatenate e per l'ordinamento esterno. Lo svantaggio è la sua memoria extra O(n).Qual è la differenza tra merge sort e quicksort?
Sono entrambi ordinamenti divide et impera, ma il quicksort partiziona attorno a un pivot e ordina in loco con
O(log n) di spazio sullo stack, mentre il merge sort divide a metà senza guardare i valori e fonde usando un buffer O(n). In pratica il quicksort di solito è più veloce grazie alla località della cache, ma il merge sort ha un caso peggiore O(n log n) garantito ed è stabile.Quando conviene usare il merge sort in pratica?
Scegli il merge sort quando ti serve un ordinamento stabile con un limite
O(n log n) garantito, quando ordini liste concatenate (dove non ha bisogno di accesso casuale) o quando fai l'ordinamento esterno di dati troppo grandi per stare in memoria. Evitalo quando la memoria scarseggia, perché gli serve O(n) di spazio extra.Il merge sort ordina in loco?
No. Il merge sort standard alloca un buffer temporaneo
O(n) per fondere le due metà, quindi non è in loco. Esistono varianti di fusione in loco, ma sono complesse e più lente o perdono la stabilità, quindi la versione con buffer è la scelta comune.Risorse correlate
Altre visualizzazioni
