3-way Merge Sort (Sắp xếp trộn 3 đường) trong C++

Merge sort chia mảng thành 2 phần, sắp xếp và gộp. Biến thể 3-way merge sort chia mảng thành 3 phần thay vì 2.

Merge sort chia đệ quy mảng thành nửa. 3-way merge sort chia thành ba phần (kích thước n/3).

Ví dụ

Input: 46, -1, -44, 79, 31, -41, 11, 20, 74, 94
Output: -44 -41 -1 11 20 31 46 74 79 94
Input: 24, -18 → Output: -18 24

Độ phức tạp thời gian: n log₃n.

Chương trình C++

// 3-way Merge Sort
#include <bits/stdc++.h>
using namespace std;

void merge1(int gArray1[], int low1, int mid1, int mid2, int high1, int destArray1[]) {
    int i = low1, j = mid1, k = mid2, l = low1;
    while ((i < mid1) && (j < mid2) && (k < high1)) {
        if (gArray1[i] < gArray1[j]) {
            if (gArray1[i] < gArray1[k]) destArray1[l++] = gArray1[i++];
            else destArray1[l++] = gArray1[k++];
        } else {
            if (gArray1[j] < gArray1[k]) destArray1[l++] = gArray1[j++];
            else destArray1[l++] = gArray1[k++];
        }
    }
    while ((i < mid1) && (j < mid2)) {
        if (gArray1[i] < gArray1[j]) destArray1[l++] = gArray1[i++];
        else destArray1[l++] = gArray1[j++];
    }
    while ((j < mid2) && (k < high1)) {
        if (gArray1[j] < gArray1[k]) destArray1[l++] = gArray1[j++];
        else destArray1[l++] = gArray1[k++];
    }
    while ((i < mid1) && (k < high1)) {
        if (gArray1[i] < gArray1[k]) destArray1[l++] = gArray1[i++];
        else destArray1[l++] = gArray1[k++];
    }
    while (i < mid1) destArray1[l++] = gArray1[i++];
    while (j < mid2) destArray1[l++] = gArray1[j++];
    while (k < high1) destArray1[l++] = gArray1[k++];
}

void mergeSort3WayRec(int gArray1[], int low1, int high1, int destArray1[]) {
    if (high1 - low1 < 2) return;
    int mid1 = low1 + ((high1 - low1) / 3);
    int mid2 = low1 + 2 * ((high1 - low1) / 3) + 1;
    mergeSort3WayRec(destArray1, low1, mid1, gArray1);
    mergeSort3WayRec(destArray1, mid1, mid2, gArray1);
    mergeSort3WayRec(destArray1, mid2, high1, gArray1);
    merge1(destArray1, low1, mid1, mid2, high1, gArray1);
}

void mergeSort3Way(int gArray1[], int n1) {
    if (n1 == 0) return;
    int fArray1[n1];
    for (int i = 0; i < n1; i++) fArray1[i] = gArray1[i];
    mergeSort3WayRec(fArray1, 0, n1, gArray1);
    for (int i = 0; i < n1; i++) gArray1[i] = fArray1[i];
}

int main() {
    int data1[] = {46, -1, -44, 79, 31, -41, 11, 20, 74, 94};
    mergeSort3Way(data1, 10);
    cout << "After 3 way merge sort: ";
    for (int i = 0; i < 10; i++) cout << data1[i] << " ";
    return 0;
}

Kết quả

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