Data Structures, Algorithms, & Applications in C++
Chapter 18, Exercise 45

As was the case for the insertion-sort decision tree, we use the notation i:j to denote a comparison between a[i] and a[j]. The element/array indexes are [0123]. In merge sort, the segments [01] and [23] are sorted first and then merged together to form the sorted sequence. The decision tree is: 

                                                            0:1
                                  ________________________/     \
                                 |                               R
                                2:3
            __________________/     \__________________
           |                                           |
          0:2                                         0:3
        /     \                                     /     \
      /        \                                   /       \
    1:2        0:3                               1:3       0:2
   /   \      /   \                             /   \     /   \
  /     \    /     \                           /     \   /     \
0123   1:3  2301   1:3                     0132     1:2  3201   1:2
      /   \       /   \                            /   \       /   \
     /     \     /     \                          /     \     /     \
  0213   0231  2013   2031                    0312     0321  3012   3021


where the right subtree R is 

                                2:3
            __________________/     \__________________
           |                                           |
          1:2                                         1:3
        /     \                                     /     \
      /        \                                   /       \
    0:2        1:3                               0:3       1:2
   /   \      /   \                             /   \     /   \
  /     \    /     \                           /     \   /     \
1023   0:3  2310   0:3                     1032     0:2  3210   0:2
      /   \       /   \                            /   \       /   \
     /     \     /     \                          /     \     /     \
  1203   1230  2103   2130                    1302     1320  3102   3120