Mergesort
Stabil sortering
Mergesort er en gratis C Academy-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.
Stabil sortering
Flettsortering er en del-og-hersk-sortering, der deler arrayet i to, sorterer hver halvdel og derefter fletter dem sammen igen. Den er O(n log n) i alle tilfælde og stabil.
Delingstrinnet
Del arrayet rekursivt ved midtpunktet, indtil hvert stykke har ét element. Et enkelt element er trivielt sorteret, og det er basistilfældet.
Fletningstrinnet
Den centrale operation fletter to allerede sorterede sekvenser til én. Gå gennem begge med indekspegere, og kopiér altid det mindste første element som det næste.
#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;
}Hvorfor den er stabil
Fletningen bruger a[i] <= a[j], så den tager elementet fra den venstre sekvens først, når to elementer er ens. Da den venstre sekvens indeholdt de tidligste elementer, bevares den oprindelige rækkefølge.
Den rekursive driver
Flettsortering kalder sig selv rekursivt på hver halvdel og fletter derefter resultaterne. Vi sender en fælles midlertidig buffer med for at undgå allokering ved hvert kald.
#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;
}Hukommelsesforbrug
I modsætning til quicksort kræver flettsortering O(n) ekstra hukommelse til flettebufferen. Det er den største ulempe ved meget store arrays, når hukommelsen er begrænset.
Garanteret O(n log n)
Rekursionen deler altid i to, hvilket giver log n niveauer, og hvert niveau fletter n elementer. Derfor er flettsortering O(n log n) i bedste, gennemsnitlige og værste tilfælde, i modsætning til quicksort.
Optælling af fletteniveauer
Antallet af rekursionsniveauer er ceil(log2 n). Lad os beregne det for flere størrelser.
#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;
}Flettsortering nedefra og op
En iterativ variant fletter sekvenser med størrelsen 1, derefter 2 og så 4, hvor størrelsen fordobles ved hver gennemløb. Den undgår rekursion helt og egner sig godt til sammenkædede lister.
#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;
}Hvornår skal du vælge flettsortering
Vælg helst flettsortering, når du har brug for:
- Garanteret O(n log n) uden dårlige tilfælde
- Stabilitet
- Sortering af sammenkædede lister (ingen tilfældig adgang nødvendig)
- Ekstern sortering af data, der er for store til RAM
Flettsortering kontra quicksort
Quicksort er normalt hurtigere i praksis og sorterer på stedet, men er ustabil og kan have et dårligt værst tænkeligt tilfælde. Flettsortering er stabil med en garanteret grænse, men bruger ekstra hukommelse. Vælg ud fra dine begrænsninger.
Hurtigt tjek
Test din forståelse af flettsortering.
Opsummering
Du har lært flettsortering.
- Del i to, sortér hver del, og flet derefter
- Fletningen vælger den venstre først for ens nøgler, hvilket giver stabilitet
- Garanteret O(n log n) i alle tilfælde
- Bruger O(n) ekstra hukommelse og er velegnet til sammenkædede lister og ekstern sortering
Lær C med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 39
- Lektioner
- 144
Ofte stillede spørgsmål
Er lektionen “Mergesort” gratis?
Ja — hele teksten til “Mergesort” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Mergesort”?
Stabil sortering Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på C Academy?
Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Mergesort”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne C Academy-lektion?
Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.