When will the worst case of Merge Sort occur?

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 ConquerInput 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 

Algorithm

A neat algorithm one of my professors gave me solves this using an opposite approach. Rather than splitting the initial array into smaller and smaller blocks, you can start with a base case and follow a recursive pattern.

Base case is [1] and [2, 1], which are the examples for worst case arrays of size 1 and 2. From that you build arrays for 3 and 4 as follows.

1. Take two arrays of sizes n and m, such that n + m = x, where x is the size you're looking for
2. Combine them, with the the array of smaller size put at the top
3. Double every element in the top array
4. Double every element and subtract 1 from the bottom array

Using this algorithm, here's the series of steps for arrays of size 3 and 4.

Examples

Size 3

1. Take [1] + [2, 1]
2. You get [1 | 2, 1]
3. [2 | 2, 1]
4. [2 | 3, 1] -> [2, 3, 1]

Size 4

1. Take [2, 1] + [2, 1]
2. You get [2, 1 | 2, 1]
3. [4, 2 | 2, 1]
4. [4, 2 | 3, 1] -> [4, 2, 3, 1]

Size 7

1. Take [2, 3, 1] + [4, 2, 3, 1]
2. You get [2, 3, 1 | 4, 2, 3, 1]
3. [4, 6, 2 | 4, 2, 3, 1]
4. [4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]

It's easy to see how you can take this approach and easily build up to huge array sizes.

Program

Here's a python function that implements this algorithm.

import mathdef worstCaseArrayOfSize(n):    if n == 1:        return [1]    else:        top = worstCaseArrayOfSize(int(math.floor(float(n) / 2)))        bottom = worstCaseArrayOfSize(int(math.ceil(float(n) / 2)))        return map(lambda x: x * 2, top) + map(lambda x: x * 2 - 1, bottom)