1. ## Merge Sort Algorithm

I know that in the worst case the merge sort algorithm takes theta(n lg n) to complete.

I know that when sorting an array of size 6 the maximum number of comparisons required is 11.

How can I figure the minimum number of comparisons to sort an array of size 6?

pwr

2. Originally Posted by pwr_hngry
I know that in the worst case the merge sort algorithm takes theta(n lg n) to complete.

I know that when sorting an array of size 6 the maximum number of comparisons required is 11.

How can I figure the minimum number of comparisons to sort an array of size 6?

pwr
The minimum number of comparisons occurs when the array is already in
sorted order. Now look at the tree of splits of the array into sub-arrays
and count the number of comparisons needed in the merge step when
the left sub-array contains elements all less than each of the elements of the
right-sub array.

If the sub-arrays both contain single elements 1 comparison is made

If the left sub-array contains 1 element and the right sub-array 2 elements then 1 comparison is made

If both sub-arrays contain 3 elements then 3 comparisons are needed.

The merges in the decomposition tree for an array of size 6 is comprised
of merges from the above list, and by adding up the comparisons for the
required merges you will get the answer you need.

(I make it 2 merges of type (1,1), two merges of type (1,2), and one
merge of type (3,3) to give a total of 7 comparisons).

RonL