Question

Please help me to solve the problem with java language!

An implementation of the Merge Sort algorithm. Modify the algorithm so that it splits the list into 3 sublists (instead of two). Each sublist should contain about n/3 items. The algorithm should sort each sublist recursively and merge the three sorted sublists. The traditional merge sort algorithm has an average and worst-case performance of O(n log₂ n). What is the performance of the 3-way Merge Sort algorithm?

Merge Sort algorithm

import java.util.Arrays;

public class MergeSort

{

public static void main(String[] args)

{

int[] values = new int[15];

for(int i=0; i<values.length; i++)

values[i] = (int)(90*Math.random())+10;

System.out.println("Unsorted: " + Arrays.toString(values));

sort(values);

System.out.println(" Sorted: " + Arrays.toString(values));

}

public static void sort(int[] data)

{

sort(data, 0, data.length-1);

}

private static void sort(int[] data, int min, int max)

{

if(max>min)

{

int pivot = (min+max)/2;

sort(data, min, pivot);

sort(data, pivot+1, max);

int left = min; //the beginning of the left sublist

int right = pivot+1; //the beginning of the right sublist

int[] merged = new int[max-min+1];

for(int i=0; i<merged.length; i++)

{

if(left<=pivot && (right>max || data[left]<data[right]))

merged[i] = data[left++];

else

merged[i] = data[right++];

}

for(int i=0, j=min; i<merged.length; i++, j++)

data[j] = merged[i];

// System.out.println(" Sorting: " + Arrays.toString(data) + " " + min + "-" + max);

}

}

}

Answer 1

The modified Java code is given below:

import java.util.Arrays;

public class MergeSort
{
    public static void main(String[] args)
    {
        int[] values = new int[15];
        for(int i=0; i<values.length; i++)
            values[i] = (int)(90*Math.random())+10;
        System.out.println("Unsorted: " + Arrays.toString(values));
        sort(values);
        System.out.println(" Sorted: " + Arrays.toString(values));
    }
    public static void sort(int[] data)
    {
        sort(data, 0, data.length-1);
    }
    private static void sort(int[] data, int min, int max)
    {
        if(max>min)
        {
            /**
             * We divide the list into three sublists left , middle and  right
             */
            int pivot = (int) Math.ceil((1.0*(max - min + 1)) / 3);
            /**
             * for left sublist --
             *     min  --  min
             *     max --- min + pivot - 1
             */
            int left_end = min + pivot - 1;
            sort(data, min, left_end);
            /**
             * for middle sublist --
             *     min  --  min + pivot 
             *     max  -- min + (2*pivot) - 1
             */
            int middle_end = min + (2*pivot) -1;
            sort(data, min + pivot, middle_end);
            /**
             * for right sublist --
             *     min  --  min + (2*pivot)
             *     max --- max
             */
            sort(data, min + (2*pivot), max);
            int left = min; //the beginning of the left sublist
            int middle = min + pivot; //the beginning of the middle sublist
            int right = min + (2*pivot); //the beginning of the right sublist
            int[] merged = new int[max-min+1];
            for(int i=0; i<merged.length; i++) // merging the three sorted sublists
            {
                if(left<=left_end && (middle>middle_end || data[left]<data[middle]) && (right>max || data[left]<data[right]))
                    merged[i] = data[left++];
                else if(middle<=middle_end && (right>max || data[middle]<data[right]))
                    merged[i] = data[middle++];
                else
                    merged[i] = data[right++];
            }
            for(int i=0, j=min; i<merged.length; i++, j++)
                data[j] = merged[i];
// System.out.println(" Sorting: " + Arrays.toString(data) + " " + min + "-" + max);
        }
    }
}

Sample Output:
Unsorted: [93, 97, 31, 50, 79, 62, 26, 81, 98, 16, 40, 50, 60, 66, 15]
Sorted: [15, 16, 26, 31, 40, 50, 50, 60, 62, 66, 79, 81, 93, 97, 98]

Screenshot of the code is given below:

The performance of the 3-way Merge Sort algorithm will be : as the depth of the recursion tree will be .

If the answer helped please upvote, it means a lot and for any query please comment.