Question

Merge Sort Algorithm Question

Can someone provide pseudocode of an algorithm that takes a sorted array into an unsorted array that causes merge sort algorithm to have the biggest runtime or worst case; an array that requires the most number of comparisons using merge sort.

A runtime analysis of the provided pseudocode will be appreciated.

Answer 1

I know that worst case on mergesort is O(nlogn), the same as the average case.

However, if the data are ascending or descending, this results to the minimum number of comparisons, and therefore mergesort becomes faster than random data. So my question is: What kind of input data produces the maximum number of comparisons that result to mergesort to be slower?

The answer at this question says:

For some sorting algorithms (e.g. quicksort), the initial order of the elements can affect the number of operations to be done. However it doesn't make any change for mergesort as it will have to do exactly the same number of operations anyway: recursively divide into small arrays and then merge them back, in total Θ(nlogn) time.

However this is wrong. At the point we have two subarrays and we want to merge them if the initial data are sorted we will have only n/2 comparisons. That is all the elements of the first subarray with only the first element of the second array. However we can achieve more than that. I'm looking for that input data.

The worst case of merge sort will be the one where merge sort will have to do maximum number of comparisons.

So I will try building the worst case in bottom up manner:

1. Suppose the array in final step after sorting is {0,1,2,3,4,5,6,7}

2. For worst case the array before this step must be {0,2,4,6,1,3,5,7} because here left subarray={0,2,4,6} and right subarray={1,3,5,7} will result in maximum comparisons.(Storing alternate elemets in left and right subarray)

   Reason: Every element of array will be compared atleast once.

3. Applying the same above logic for left and right subarray for previous steps : For array {0,2,4,6} the worst case will be if the previous array is {0,4} and {2,6} and for array {1,3,5,7} the worst case will be for {1,5} and {3,7}.

4. Now applying the same for previous step arrays: For worst cases: {0,4} must be {4,0} , {2,6} must be {6,2} ,{1,5}must be {5,1} {3,7} must be {7,3} . Well if you look clearly this step is not necessary because if the size of set/array is 2 then every element will be compared atleast once even if array of size 2 is sorted.

Now going top down and analyzing the situation

Applying Merge Sort using Divide and Conquer

Input array arr[] = [4,0,6,2,5,1,7,3]
                           /  \
                          /    \
                  [4,0,6,2] and [5,1,7,3]
                     / \           / \
                    /   \         /   \
                 [4,0] [6,2]    [5,1] [7,3]       Every pair of 2 will be compared atleast once therefore maximum comparison here
                   |     |        |     |
                   |     |        |     |
                 [0,4] [2,6]    [1,5] [3,7]      Maximum Comparison:Every pair of set is used in comparison     
                   \     /        \     /                        
                    \   /          \   /
                 [0,2,4,6]      [1,3,5,7]        Maximum comparison again: Every pair of set compared
                      \             /
                       \           / 
                     [0,1,2,3,4,5,6,7]          

Now you can apply the same logic for any array of size n

Below is the program which implements the above logic.

Note:The below program isn't valid for powers of 2 only. It is a generalized method to provide the worst case for any array of size n. You can try different arrays for input by yourself.

class MergeWorstCase
{
    public static void print(int arr[])
    {
        System.out.println();
        for(int i=0;i<arr.length;i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }
    public static void merge(int[] arr, int[] left, int[] right) {
        int i,j;
        for(i=0;i<left.length;i++)
                arr[i]=left[i];
        for(j=0;j<right.length;j++,i++)
                arr[i]=right[j];
    }

    //Pass a sorted array here
    public static void seperate(int[] arr) { 

            if(arr.length<=1)
                return;

            if(arr.length==2)
            {
                int swap=arr[0];
                arr[0]=arr[1];
                arr[1]=swap;
                return;
            }

        int i,j;
        int m = (arr.length + 1) / 2;
        int left[] = new int[m];
        int right[] = new int[arr.length-m];

        for(i=0,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in left subarray
            left[j]=arr[i];

        for(i=1,j=0;i<arr.length;i=i+2,j++) //Storing alternate elements in right subarray
            right[j]=arr[i];

        seperate(left);
        seperate(right);
        merge(arr, left, right);
    }
    public static void main(String args[])
    {
        int arr1[]={0,1,2,3,4,5,6,7};
        seperate(arr1);
        System.out.print("For array 1:");
        print(arr1);
        int arr2[]={0,1,2,3,4,5,6,7,8};
        seperate(arr2);
        System.out.print("For array 2:");
        print(arr2);            
    }
}

Output:

For array 1:
4 0 6 2 5 1 7 3 
For array 2:
8 0 4 6 2 5 1 7 3