মার্জ সর্টে অ্যারেটিকে 2টি অংশে বিভক্ত করা, বাছাই করা এবং শেষ পর্যন্ত তাদের মার্জ করা জড়িত। মার্জ সাজানোর একটি বৈকল্পিককে 3-ওয়ে মার্জ সাজানোর হিসাবে বিবেচনা করা হয় যেখানে অ্যারেটিকে 2 ভাগে ভাগ করার পরিবর্তে আমরা এটিকে 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
3 ওয়ে মার্জ সাজানোর সময় জটিলতা হল nlog3 n.
উদাহরণ
// C++ Program for performing 3 way Merge Sort
#include <bits/stdc++.h>
usingnamespacestd;
voidmerge1(intgArray1[], intlow1, intmid1,
intmid2, inthigh1, intdestArray1[]){
inti = low1, j = mid1, k = mid2, l = low1;
// choose smaller of the smallest in the three ranges
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 < high)
destArray1[l++] = gArray1[k++];
}
voidmergeSort3WayRec(intgArray1[], intlow1,
inthigh1, intdestArray1[]){
if(high1 - low1 < 2)
return;
intmid1 = low1 + ((high1 - low1) / 3);
intmid2 = low1 + 2 * ((high1 - low1) / 3) + 1;
mergeSort3WayRec(destArray1, low1, mid1, gArray1);
mergeSort3WayRec(destArray1, mid1, mid2, gArray1);
mergeSort3WayRec(destArray1, mid2, high1, gArray1);
merge(destArray1, low1, mid1, mid2, high1, gArray1);
}
voidmergeSort3Way(intgArray1[], intn1){
if(n1 == 0)
return;
intfArray1[n];
for(inti = 0; i < n1; i++)
fArray1[i] = gArray1[i];
// sort function
mergeSort3WayRec(fArray1, 0, n, gArray1);
for(inti = 0; i < n1; i++)
gArray1[i] = fArray1[i];
}
// Driver Code
intmain(){
intdata1[] = {46, -1, -44, 79, 31,
-41, 11, 20, 74, 94};
mergeSort3Way(data1,10);
cout<< "After 3 way merge sort: ";
for(inti = 0; i < 10; i++){
cout<< data1[i] << " ";
}
return0;
} আউটপুট
After 3 way merge sort: -44 -41 -1 11 20 31 46 74 79 94
