หาการจัดเรียงที่ทำให้ Merge Sort ทำงานช้าที่สุด (worst case) ใน C++

หาการจัดเรียง (permutation) ของชุดตัวเลขที่ทำให้ Merge Sort ต้องทำการเปรียบเทียบมากที่สุด แม้ว่าเวลาสับซ้อนจะเป็น O(n log n) เสมอ

แนวคิด

สร้างการจัดเรียงแบบ "worst case" โดยการแบ่งอาร์เรย์สลับกัน (alternating split) แล้วเรียงย่อยๆ แบบเวียนเกิด

ตัวอย่าง

อินพุต: {11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26}

เอาต์พุต: {11,19,15,23,13,21,17,25,12,20,16,24,14,22,18,26}

อัลกอริธึม

1. divide(): แยกอาร์เรย์เป็น left (index คู่) และ right (index คี่)
2. gen_worst_seq(): เรียก divide แล้ว gen_worst_seq แบบเวียนเกิดสำหรับ left และ right
3. merge(): รวม left และ right กลับเข้า arr

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void display(int A[], int size) {
    for (int i = 0; i < size; i++) cout << A[i] << " ";
    cout << endl;
}

void merge(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
    int i;
    for (i = 0; i <= m_index - l_index; i++) arr[i] = left[i];
    for (int j = 0; j < r_index - m_index; j++) arr[i + j] = right[j];
}

void divide(int arr[], int left[], int right[], int l_index, int m_index, int r_index) {
    for (int i = 0; i <= m_index - l_index; i++) left[i] = arr[i * 2];
    for (int i = 0; i < r_index - m_index; i++) right[i] = arr[i * 2 + 1];
}

void gen_worst_seq(int arr[], int l_index, int r_index) {
    if (l_index < r_index) {
        int m_index = l_index + (r_index - l_index) / 2;
        int left[m_index - l_index + 1];
        int right[r_index - m_index];
        divide(arr, left, right, l_index, m_index, r_index);
        gen_worst_seq(left, l_index, m_index);
        gen_worst_seq(right, m_index + 1, r_index);
        merge(arr, left, right, l_index, m_index, r_index);
    }
}

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]);
    gen_worst_seq(arr, 0, n - 1);
    display(arr, n);
    return 0;
}

ผลลัพธ์

11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26