Mergesort

การเรียงลำดับแบบคงลำดับเดิม

ขั้นตอนการแบ่ง

ขั้นตอนการผสาน

#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;
}

เหตุผลที่คงลำดับเดิม

ตัวควบคุมการเรียกซ้ำ

#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;
}

การใช้หน่วยความจำ

รับประกัน O(n log n)

การนับระดับการผสาน

#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 จากล่างขึ้นบน

#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;
}

เมื่อใดควรเลือก Mergesort

Mergesort เทียบกับ Quicksort

ตรวจสอบความเข้าใจอย่างรวดเร็ว

สรุปทบทวน