3-way mergesort如何可视化？

Question

[6, 4, 3, 7, 2, 9, 1, 5]
[6, 4], [3, 7, 2], [9, 1, 5]
[6, 4], [3], [7], [2], [9], [1], [5] 
swap
[6, 4], [3], [7], [2], [9], [1], [5] 
[4, 6], [2, 3, 7], [1, 5, 9]
[2, 3, 4, 6, 7], [1, 5, 9]
[1, 2, 3, 4, 5, 6, 7, 9]

这是正确的吗？为什么这个n对数底是3n？

Answer 1

合并操作应该是3种方式：

[6] [4] [3] [7] [2] [9] [1] [5] 
[3   4   6] [2   7   9] [1   5]
[1   2   3   4   5   6   7   9]

|N|J|H|Q|6|L|K|5|P|E|3|A|G|8|D|4|O|I|B|0|9|M|F|2|1|C|7|
|H J N|6 L Q|5 K P|3 A E|8 D G|4 I O|0 9 B|2 F M|1 7 C|
|5 6 H J K L N P Q|3 4 8 A D E G I O|0 1 2 7 9 B C F M|
|0 1 2 3 4 5 6 7 8 9 A B C D E F G H I J K L M N O P Q|