3-Way Merge Sort ใน C++

ภาพรวม

3-Way Merge Sort เป็นรูปแบบของ Merge Sort ที่แบ่ง Array เป็น 3 ส่วน แทนที่จะเป็น 2 ส่วน (Standard Merge Sort)

อัลกอริทึม

1. Divide: แบ่ง Array เป็น 3 ส่วนประมาณเท่ากัน (n/3)
2. Conquer: เรียงแต่ละส่วน Recursively
3. Merge: รวม 3 Sorted Arrays ให้เป็น 1 Sorted Array

Merge 3 Sorted Arrays

ใช้ 3 Pointers (i, j, k) เลือกค่าน้อยสุดจาก 3 ส่วนทีละขั้นตอน

Complexity Analysis

• Recurrence: T(n) = 3T(n/3) + O(n)
• Master Theorem: a=3, b=3, f(n)=n → log₃3 = 1 → Case 2: O(n log₃ n)
• เทียบกับ 2-Way: O(n log₂ n) → 3-Way เร็วกว่าเล็กน้อย (log base ใหญ่กว่า)
• แต่ Constant Factor ใหญ่กว่า (Merge 3-way ซับซ้อนกว่า)

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

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

// Merge 3 sorted subarrays: [low..mid1), [mid1..mid2), [mid2..high)
void merge3(int arr[], int low, int mid1, int mid2, int high, int dest[]) {
    int i = low, j = mid1, k = mid2, l = low;

    // Merge while all three have elements
    while (i < mid1 && j < mid2 && k < high) {
        if (arr[i] <= arr[j] && arr[i] <= arr[k]) dest[l++] = arr[i++];
        else if (arr[j] <= arr[i] && arr[j] <= arr[k]) dest[l++] = arr[j++];
        else dest[l++] = arr[k++];
    }

    // Merge remaining two
    while (i < mid1 && j < mid2) dest[l++] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
    while (j < mid2 && k < high) dest[l++] = (arr[j] <= arr[k]) ? arr[j++] : arr[k++];
    while (i < mid1 && k < high) dest[l++] = (arr[i] <= arr[k]) ? arr[i++] : arr[k++];

    // Copy remaining single
    while (i < mid1) dest[l++] = arr[i++];
    while (j < mid2) dest[l++] = arr[j++];
    while (k < high) dest[l++] = arr[k++];
}

void mergeSort3WayRec(int src[], int low, int high, int dest[]) {
    if (high - low < 2) return;  // 0 or 1 element

    int mid1 = low + (high - low) / 3;
    int mid2 = low + 2 * (high - low) / 3 + 1;

    // Recursive calls (swap src/dest for in-place feel)
    mergeSort3WayRec(dest, low, mid1, src);
    mergeSort3WayRec(dest, mid1, mid2, src);
    mergeSort3WayRec(dest, mid2, high, src);

    // Merge from dest back to src
    merge3(dest, low, mid1, mid2, high, src);
}

void mergeSort3Way(int arr[], int n) {
    if (n == 0) return;
    vector<int> temp(arr, arr + n);
    mergeSort3WayRec(temp.data(), 0, n, arr);
}

int main() {
    int data[] = {46, -1, -44, 79, 31, -41, 11, 20, 74, 94};
    int n = sizeof(data) / sizeof(data[0]);

    mergeSort3Way(data, n);

    cout << "After 3-way merge sort: ";
    for (int i = 0; i < n; i++) cout << data[i] << " ";
    cout << endl;
    return 0;
}

ผลลัพธ์

After 3-way merge sort: -44 -41 -1 11 20 31 46 74 79 94

คำอธิบายเพิ่มเติม

• ใช้ Double Buffering (src/dest Swap) หลีกเลี่ยง Copy ทุกครั้ง
• Base Case: Size < 2 (Already Sorted)
• Mid Points: mid1 = low + n/3, mid2 = low + 2n/3 + 1
• ในทางปฏิบัติ 2-Way Merge Sort ใช้มากกว่า เนื่องจาก:
  • โค้ดง่ายกว่า
  • Cache Performance ดีกว่า (Sequential Access)
  • Constant Factor ต่ำกว่า
• 3-Way เหมาะสำหรับ External Sorting (Tape/Disk) ที่ Seek Time สำคัญ

Generalization: k-Way Merge Sort

• Time: O(n logₖ n)
• Optimal k ขึ้นอยู่กับ Hardware (Cache Line, Memory Bandwidth)
• External Sorting: k = จำนวน Tape Drives / Buffers