सी ++ में 3-तरफा मर्ज सॉर्ट करें

मर्ज सॉर्ट में सरणी को 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 तरह से मर्ज सॉर्ट की समय जटिलता nlog है₃ 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