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

Cho tập các phần tử đã sắp xếp. Tìm hoán vị của chúng khiến thuật toán Merge Sort tiêu chuẩn thực hiện số lần so sánh tối đa (trường hợp xấu nhất).

Ví dụ

Input: [11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26]

Output: [11, 19, 15, 23, 13, 21, 17, 25, 12, 20, 16, 24, 14, 22, 18, 26]

Ý tưởng thuật toán

Merge Sort chia mảng thành 2 nửa, sắp xếp đệ quy, sau đó merge. Để maximize so sánh khi merge, ta muốn 2 nửa con "xen kẽ" nhau tối đa khi merge.

Đệ quy xây dựng từ dưới lên:

1. Chia mảng thành 2 nửa: left (chỉ số chẵn), right (chỉ số lẻ).
2. Đệ quy sắp xếp left và right theo cùng chiến lược.
3. Merge: xen kẽ phần tử từ left và right.

Mã nguồn 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_idx, int m_idx, int r_idx) {
    int i = 0;
    for (; i <= m_idx - l_idx; i++) arr[i] = left[i];
    for (int j = 0; j < r_idx - m_idx; j++) arr[i + j] = right[j];
}

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

void genWorstSeq(int arr[], int l_idx, int r_idx) {
    if (l_idx < r_idx) {
        int m_idx = l_idx + (r_idx - l_idx) / 2;
        int leftSize = m_idx - l_idx + 1;
        int rightSize = r_idx - m_idx;
        
        vector left(leftSize), right(rightSize);
        
        divide(arr, left.data(), right.data(), l_idx, m_idx, r_idx);
        genWorstSeq(left.data(), l_idx, m_idx);
        genWorstSeq(right.data(), m_idx + 1, r_idx);
        merge(arr, left.data(), right.data(), l_idx, m_idx, r_idx);
    }
}

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

Kết quả chạy chương trình

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

Giải thích quy trình (n=8)

Mảng gốc: [a0, a1, a2, a3, a4, a5, a6, a7]

Cấp 1: divide → left=[a0,a2,a4,a6], right=[a1,a3,a5,a7]
Cấp 2: left divide → [a0,a4], [a2,a6]; right divide → [a1,a5], [a3,a7]
Cấp 3: Mỗi cặp 2 phần tử divide → [a0],[a4] v.v.
Merge ngược lại xen kẽ:
[a0,a4] → merge → [a0,a4] (đã xen kẽ)
[a2,a6] → merge → [a2,a6]
[a0,a4,a2,a6] merge → [a0,a2,a4,a6]
Tương tự right: [a1,a3,a5,a7]
Merge cuối: [a0,a1,a2,a3,a4,a5,a6,a7] - nhưng xen kẽ tối đa khi merge

Độ phức tạp

• Thời gian tạo hoán vị: O(N log N) - giống Merge Sort.
• Không gian: O(N log N) do đệ quy và mảng tạm.

Lưu ý

• Merge Sort vẫn chạy O(N log N) về mặt渐近, nhưng hằng số so sánh lớn nhất.
• Code dùng VLA (variable-length array) `int left[...]` không chuẩn C++. Đã sửa dùng `vector` trong code trên.
• Đối với mảng không phải lũy thừa 2, logic vẫn hoạt động đúng.