Tìm hoán vị gây trường hợp xấu nhất của Merge Sort trong C

Cho tập phần tử đã sắp xếp, tìm hoán vị nào khiến Merge Sort thực hiện nhiều so sánh nhất (trường hợp xấu nhất thực tế dù độ phức tạp vẫn O(n log n)).

Ví dụ

Mảng đã sắp xếp: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Mảng đầu vào gây worst case: 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

Phương pháp xây dựng bottom-up

• Mảng đã sắp xếp: {11,12,13,14,15,16,17,18}
• Chia thành 2 mảng con xen kẽ: left={11,13,15,17}, right={12,14,16,18}
• Đệ quy áp dụng cùng logic cho left và right
• Ghép ngược lại

Thuật toán

GenerateWorstCase(arr, l, r):
    if l < r:
        m = (l+r)/2
        split arr thành left (phần tử chẵn) và right (phần tử lẻ)
        GenerateWorstCase(left, l, m)
        GenerateWorstCase(right, m+1, r)
        join left và right ngược vào arr

Chương trình mẫu

#include <stdio.h>
#include <stdlib.h>

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("\n");
}

void join(int arr[], int left[], int right[], int l, int m, int r) {
    int i = 0;
    for (; i <= m-l; i++) arr[i] = left[i];
    for (int j = 0; j < r-m; j++) arr[i+j] = right[j];
}

void split(int arr[], int left[], int right[], int l, int m, int r) {
    for (int i = 0; i <= m-l; i++) left[i] = arr[i*2];
    for (int i = 0; i < r-m; i++) right[i] = arr[i*2+1];
}

void generateWorstCase(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r-l)/2;
        int left[m-l+1], right[r-m];
        split(arr, left, right, l, m, r);
        generateWorstCase(left, l, m);
        generateWorstCase(right, m+1, r);
        join(arr, left, right, l, m, r);
    }
}

int main() {
    int arr[] = {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
    int n = sizeof(arr)/sizeof(arr[0]);
    printf("Mảng đã sắp xếp:\n");
    printArray(arr, n);
    generateWorstCase(arr, 0, n-1);
    printf("\nMảng gây worst case Merge Sort:\n");
    printArray(arr, n);
    return 0;
}

Kết quả

Mảng đã sắp xếp:
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Mảng gây worst case Merge Sort:
11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26