Some Type Of Mergesort

The worst case of merge sort will be the one, where the merge sort will have to do maximum number of comparisons. In order to do so, the left and right sub-array involved in merge operation should store alternate elements of sorted array. Left sub-array would be $(1,3,5,7)$ and right sub-array would be $(2,4,6,8)$ . Every element of array will be compared at least once.

We apply the same above logic for left and right sub-array. For array $(1,3,5,7)$ the worst case will be for $(1,5)$ and $(3,7)$ For the last pair of 2 we switch their position. so each will be compared at least once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

                       [1,2,3,4,5,6,7,8]      
                          /         \
                         /           \
                   [1,3, 5, 7]   [2, 4, 6, 8]         Every pair is compared
                       /   \         /   \                                   
                      /     \       /     \              
                  [1, 5] [3, 7]   [2, 6] [4, 8]           
                     |     |         |      |
                     |     |         |      |
                  [5, 1] [7,3]    [6, 2] [8, 4]      Every pair of 2 will be compared at least once 

So $(5, 1, 7, 3, 6, 2, 8, 4)$ is a permutation that gives that gives worst case. But that is not unique because order of the left and right sub-array doesn't matter. We have $2$ branches at the first divide and $4$ branches at the second divide, for a total of $2\times4=8$ possible permutations.