3-ওয়ে মার্জ সোর্ট (3-way Merge Sort) C++-এ

পরিচয়

মার্জ সোর্টে অ্যারে রিকার্সিভলি ২ ভাগে ভাগ করা হয়, সো্র্ট করে মার্জ করা হয়। 3-ওয়ে মার্জ সোর্টে অ্যারে ৩ ভাগে ভাগ করা হয়।

মার্জ সোর্টে সাবঅ্যারে আকার হাফ হয়ে যায়, 3-ওয়ে মার্জ সোর্টে আকার এক-তिहায় হয়ে যায়।

উদাহরণ

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

Time complexity: n log₃n

C++ কোড উদাহরণ

// C++ Program for performing 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; 
}

আউটপুট

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