# arrays – When will the worst case of Merge Sort occur?

Table of Contents

## arrays – 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:

- 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 isnt 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.

- Take two arrays of sizes
`n`

and`m`

, such that`n + m = x`

, where x is the size youre looking for - Combine them, with the the array of smaller size put at the top
- Double every element in the top array
- Double every element and subtract 1 from the bottom array

Using this algorithm, heres the series of steps for arrays of size `3`

and `4`

.

## Examples

### Size `3`

- Take
`[1] + [2, 1]`

- You get
`[1 | 2, 1]`

`[2 | 2, 1]`

`[2 | 3, 1] -> [2, 3, 1]`

### Size `4`

- Take
`[2, 1] + [2, 1]`

- You get
`[2, 1 | 2, 1]`

`[4, 2 | 2, 1]`

`[4, 2 | 3, 1] -> [4, 2, 3, 1]`

### Size `7`

- Take
`[2, 3, 1] + [4, 2, 3, 1]`

- You get
`[2, 3, 1 | 4, 2, 3, 1]`

`[4, 6, 2 | 4, 2, 3, 1]`

`[4, 6, 2 | 7, 3, 5, 1] -> [4, 6, 2, 7, 3, 5, 1]`

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

## Program

Heres a python function that implements this algorithm.

```
import math
def 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)
```