java i) tBased on the recursive (2-way) mergesort given below, implement a 3-way

Question

java

i) tBased on the recursive (2-way) mergesort given below, implement a 3-way recursive mergesort algorithm. In the 3-way mergesort algorithm, the part of the array delimited by low and high will need to be divided into three subarrays and recursive calls made on each of them. Then the three subarrays will need to be merged into one sorted one. Also analyse the time complexity of the 3- way mergesort algorithm and compare it with that of (2-way) mergesort. public static void Mergesort (int[] a, int low, int high) low and high delimit the part of the array which is to be sorted. if there is only one element the array is already sorted. if (low high) Find where to split the array int mid (low high)/2. Solve the subproblems Mergesort (a, Low, mid); Mergesort (a, mid 1 high); Combine the solutions Merge (a, Low, mid, high);

Explanation / Answer

Program:

public class MergeSort3Way {
  
   public static int getElement(int a[], int ind) {
       if (ind < a.length)
           return a[ind];
       else
           return Integer.MAX_VALUE;  
   }
private static void merge(int[] a1, int[] a2, int[] a3, int[] dest) {
      
       int s = getElement(a1, 0);
       int m = getElement(a2, 0);
       int e = getElement(a3, 0);
       // indexes of the above source elements in their arrays
       int src1 = 0;
       int src2 = 0;
       int src3 = 0;
      
          
       int destIndex = 0;
      
      
       while (destIndex < dest.length) {
           if (s <= m) {
               if (e <= s) { // srcElt3 is the smallest
                   dest[destIndex] = e;
                   src3++;
                   e = getElement(a3, src3);                  
               }
               else { // srcElt1 is the smallest
                   dest[destIndex] = s;
                   src1++;
                   s = getElement(a1, src1);                      
               } // end if              
           }
           else { // srcElt2 < srcElt1
               if (e <= m) { // srcElt3 is the smallest
                   dest[destIndex] = e;
                   src3++;
                   e = getElement(a3, src3);                  
               }
               else { // srcElt2 is the smallest
                   dest[destIndex] = m;
                   src2++;
                   m= getElement(a2, src2);                      
               } // end if              
           } // end if
           destIndex++;
       } // end while

   } // end merge
  
static void mergeSort(int A[]) {
       // base case: empty array or array of length 1 is already sorted
       if (A.length <= 1)
           return;
      
       int s1; // size of first & second temp arrays
       int s3; // size of third temp array
       if (A.length == 2) {
           s1 = 1;
           s3 = 0;
       }
       else {
           s1 = A.length / 3; // size of first & second temp arrays
           s3 = A.length - 2* s1; // size of third temp array
       } // end if
       int t1[] = new int[s1];
       int t2[] = new int[s1];
       int t3[] = new int[s3];
       for (int i = 0; i < s1; i++)
           t1[i] = A[i];
       for (int i = 0; i < s1; i++)
           t2[i] = A[s1+i];
       for (int i = 0; i < s3; i++)
           t3[i] = A[2*s1 + i];
      
       // sort each of the temporary arrays (recursive step)
       mergeSort(t1);
       mergeSort(t2);
       mergeSort(t3);

       // merge the temp arrays back into the original array
       merge(t1, t2, t3, A);
      
   } // end mergeSort
static void print(int arr[]) {
       for (int i = 0; i < arr.length; i++) {
           System.out.print(arr[i] + " ");
       } // end for
       System.out.println();
   } // end print
public static void main(String args[]) {
       final int LENGTH = 30;
       int array[] = new int[LENGTH];
       for (int i = 0; i < LENGTH; i++)
           array[i] = (int) (1 + Math.random() * LENGTH); // range [1..LENGTH]
       System.out.print("original array: ");
       print(array);
       mergeSort(array);
       System.out.print("sorted array: ");
       print(array);
   } // end main

}

output:

original array: 13 24 8 22 5 1 26 27 25 27 4 10 11 15 14 14 25 4 1 21 26 26 22 19 20 10 16 24 17 11
sorted array: 1 1 4 4 5 8 10 10 11 11 13 14 14 15 16 17 19 20 21 22 22 24 24 25 25 26 26 26 27 27

complexity:

n-way merge sort -> nlogn (base n)

which is O(n) + O(n)->

this for merge step which will result in linear time O(n) time for the mergesort right.
As for 3-way merge, O(nlogn (base 3))

or normal merge sort, recurrence relation comes as t(n)=2t(n/2)+ c.n. 1..... bcoz in merge function per iteration compulsory only one comparison is required ..

in case of 3 way merge ... we require 2 comparisons per iteration hence

t(n)=2t(n/2)+ c.n. 2= n + 2.c.n. log n (base 3)...eq(1)

where as in 2-way merge t(n)=2t(n/2)+ c.n. 2= n + 1.c.n. log n (base 2)...eq(2)

for some same c , put n= 512 eq (1) gives t(n)= 512 + 2.c.512.log 512 (base 3) =512+5814.64 * c eq (2) gives t(n)= 512 + 1.c.512.log 512 (base 2) =512+4608 * c hence 3 way merge is not better.

i hope this may resolve issue. please correct if mistaken Thanks

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.