Question

How many key comparisons are made by mergesort in the

a. Best case?

b. Worst Case?

Answer 1

Merge sort is a divide and conquer algorithm.

It divides the array into smaller pieces sorts the smaller pieces and combines them.

Now comaprisons only take place during merging not in splitting the array or on recursive calls.

Imagine 2 arrays of size a and b are merged

Best case comparison - min(a,b) because arrays will already be sorted in the order in which they can be combined .

Ex- all elements in array1 is less than that of first element in array 2 and both arrays are already sorted in ascending order . Size of array 1 <Size of array 2 then we need to need to compare each element of array 1 with first element of array 2 only. All elements of array 2 will be after array1 elements.

Worst case- a+b-1

When all alternate elements of each array goes into the sorted array.

Here -1 is there because comparison takes place between 2 elements and in last comparison one is smaller and the greater will then occupy the next position without any further comparison.