Mergesort
Ordinamento stabile
Mergesort è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 3 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 C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
Ordinamento stabile
Mergesort è un algoritmo di ordinamento basato su divide et impera che divide l'array a metà, ordina ciascuna metà e poi le unisce nuovamente. Ha complessità O(n log n) in ogni caso ed è stabile.
La fase di divisione
Divida ricorsivamente l'array nel punto centrale finché ogni parte contiene un solo elemento. Un singolo elemento è già ordinato per definizione: questo è il caso base.
La fase di fusione
L'operazione fondamentale unisce due sequenze già ordinate in una sola. Scorra entrambe usando puntatori agli indici, copiando ogni volta il successivo elemento iniziale più piccolo.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi)
tmp[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (int t = lo; t <= hi; t++) a[t] = tmp[t];
}
int main(void) {
int a[] = {1, 4, 6, 2, 3, 5}; /* two sorted runs */
int tmp[6];
merge(a, 0, 2, 5, tmp);
for (int i = 0; i < 6; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Perché è stabile
La fusione usa a[i] <= a[j], quindi, quando due elementi sono uguali, sceglie prima quello della sequenza sinistra. Poiché la sequenza sinistra conteneva gli elementi precedenti, l'ordine originale viene preservato.
Il controllo ricorsivo
Mergesort richiama ricorsivamente l'algoritmo su ciascuna metà e poi le unisce. Passiamo un buffer di lavoro condiviso per evitare di allocare memoria a ogni chiamata.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo, j=mid+1, k=lo;
while (i<=mid && j<=hi) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
while (i<=mid) tmp[k++]=a[i++];
while (j<=hi) tmp[k++]=a[j++];
for (int t=lo;t<=hi;t++) a[t]=tmp[t];
}
void msort(int a[], int lo, int hi, int tmp[]) {
if (lo >= hi) return;
int mid = lo + (hi - lo) / 2;
msort(a, lo, mid, tmp);
msort(a, mid + 1, hi, tmp);
merge(a, lo, mid, hi, tmp);
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8, 4};
int tmp[7];
msort(a, 0, 6, tmp);
for (int i = 0; i < 7; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Utilizzo della memoria
A differenza di quicksort, mergesort richiede memoria aggiuntiva O(n) per il buffer di fusione. Questo è il suo principale svantaggio per array molto grandi in condizioni di memoria limitata.
O(n log n) garantito
La ricorsione divide sempre a metà, producendo log n livelli, e a ogni livello unisce n elementi. Quindi mergesort è O(n log n) nei casi migliore, medio e peggiore, a differenza di quicksort.
Contare i livelli di fusione
Il numero di livelli di ricorsione è ceil(log2 n). Calcoliamolo per diverse dimensioni.
#include <stdio.h>
int levels(int n) {
int L = 0;
while (n > 1) { n = (n + 1) / 2; L++; }
return L;
}
int main(void) {
int sizes[] = {1, 2, 8, 100, 1000};
for (int i = 0; i < 5; i++)
printf("n=%d levels=%d\n", sizes[i], levels(sizes[i]));
return 0;
}Mergesort dal basso verso l'alto
Una variante iterativa unisce sequenze di dimensione 1, poi 2, poi 4, raddoppiando la dimensione a ogni passata. Evita completamente la ricorsione ed è adatta alle liste concatenate.
#include <stdio.h>
void merge(int a[], int lo, int mid, int hi, int tmp[]) {
int i=lo,j=mid+1,k=lo;
while(i<=mid&&j<=hi) tmp[k++]=(a[i]<=a[j])?a[i++]:a[j++];
while(i<=mid) tmp[k++]=a[i++];
while(j<=hi) tmp[k++]=a[j++];
for(int t=lo;t<=hi;t++) a[t]=tmp[t];
}
int main(void) {
int a[] = {5, 2, 9, 1, 3, 8}, n = 6, tmp[6];
for (int width = 1; width < n; width *= 2)
for (int lo = 0; lo < n - width; lo += 2 * width) {
int mid = lo + width - 1;
int hi = (lo + 2*width - 1 < n-1) ? lo + 2*width - 1 : n-1;
merge(a, lo, mid, hi, tmp);
}
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");
return 0;
}Quando scegliere mergesort
Preferisca mergesort quando ha bisogno di:
- O(n log n) garantito, senza casi sfavorevoli
- Stabilità
- Ordinare liste concatenate, senza accesso casuale
- Ordinamento esterno di dati troppo grandi per la RAM
Mergesort e quicksort
Quicksort è generalmente più veloce nella pratica e ordina sul posto, ma non è stabile e può avere un caso peggiore sfavorevole. Mergesort è stabile e offre un limite garantito, ma usa memoria aggiuntiva. Scelga in base ai propri vincoli.
Verifica rapida
Verifichi la propria comprensione di mergesort.
Riepilogo
Ha imparato mergesort.
- Dividere a metà, ordinare ciascuna parte e poi unirle
- La fusione sceglie prima la sequenza sinistra in caso di chiavi uguali, garantendo la stabilità
- O(n log n) garantito in tutti i casi
- Richiede memoria aggiuntiva O(n); è ideale per liste concatenate e ordinamenti esterni
Domande Frequenti
La lezione «Mergesort» è gratuita?
Sì — il testo completo di «Mergesort» è 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 C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Mergesort»?
Ordinamento stabile Eserciti C Academy 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 C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Mergesort»?
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 C Academy?
Sì. Ogni lezione C Academy 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.