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