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:
- Suppose the array in final step after sorting is
{0,1,2,3,4,5,6,7}
- 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. - 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}
. - 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