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?
The minimum number of comparisons occurs when the array is already in
Originally Posted by pwr_hngry
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
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).