Visualize Merge Sort Merge sort is a sorting algorithm which works by splitting a given list in half, recursively sorting both smaller lists, and merging them back together to one sorted list. The base case of the recursion is arriving at a singleton list, which cannot be split further but is per definition already sorted.

The execution of the algorithm on the list [1,7,6,3,3,2,5] can be visualized in the following way:

       [1,7,6,3,3,2,5]
       /             \      split
   [1,7,6,3]       [3,2,5]
    /     \        /    \   split
 [1,7]   [6,3]   [3,2]  [5]
 /   \   /   \   /   \   |  split
[1] [7] [6] [3] [3] [2] [5]
 \   /   \   /   \   /   |  merge
 [1,7]   [3,6]   [2,3]  [5]
    \     /         \   /   merge
   [1,3,6,7]       [2,3,5]
       \             /      merge
       [1,2,3,3,5,6,7]


The Task

Write a program or function which takes a list of integers in any reasonable way as input and visualizes the different partitions of this list while being sorted by a merge sort algorithm. This means you don't have to output a graph like above, but just the lists are fine:

[1,7,6,3,3,2,5]
[1,7,6,3][3,2,5]
[1,7][6,3][3,2][5]
[1][7][6][3][3][2][5]
[1,7][3,6][2,3][5]
[1,3,6,7][2,3,5]
[1,2,3,3,5,6,7]


Furthermore, any reasonable list notation is fine, therefore the following would also be a valid output:

1 7 6 3 3 2 5
1 7 6 3|3 2 5
1 7|6 3|3 2|5
1|7|6|3|3|2|5
1 7|3 6|2 3|5
1 3 6 7|2 3 5
1 2 3 3 5 6 7


Finally, the way to split a list in two smaller lists is up to you as long as the length of both resulting lists differs at most by one. That means instead of splitting [3,2,4,3,7] into [3,2,4] and [3,7], you could also split by taking elements at even and odd indexes ([3,4,7] and [2,3]) or even randomize the split every time.

This is code-golf, so the shortest code in any language measured in bytes wins.

Test cases

As noted above, the actual format and the way to split lists in half is up to you.

[10,2]
[10][2]
[2,10]

[4,17,1,32]
[4,17][1,32]
[4][17][1][32]
[4,17][1,32]
[1,4,17,32]

[6,5,4,3,2,1]
[6,5,4][3,2,1]
[6,5][4][3,2][1]
[6][5][4][3][2][1]
[5,6][4][2,3][1] &lt;- Important: This step cannot be [5,6][3,4][1,2], because 3 and 4 are on different branches in the the tree
[4,5,6][1,2,3]
[1,2,3,4,5,6]
Haskell, 137 128 127 125 121 109 106 bytes

(-2)+(-4)=(-6) bytes thanks to nimi! Changing it to collect all the steps in a list (again due to nimi) saves 12 more bytes.

Another 3 bytes due to Laikoni, with pattern guard binding and a clever use of list comprehension to encode the guard. 



import Data.List
g x|y&lt;-x&gt;&gt;=h=x:[z|x/=y,z&lt;-g y++[sort&lt;$&gt;x]]
h[a]=[[a]]
h x=foldr(\x[b,a]-&gt;[x:a,b])[[],[]]x


Try it online!

Splitting the lists into the odd and the even positioned elements is a shorter code than into the two sequential halves, because we're spared having to measure the length, then.

Works by "printing" the lists, then recursing with the split lists (x &gt;&gt;= h) if there actually was any splitting done, and "printing" the sorted lists; starting with the one input list; assuming the non-empty input. And instead of actual printing, just collecting them in a list.

The list produced by g[[6,5..1]], printed line-by-line, is:

[[6,5,4,3,2,1]]
[[6,4,2],[5,3,1]]
[[6,2],[4],[5,1],[3]]
[[6],[2],[4],[5],[1],[3]]
[[2,6],[4],[1,5],[3]]
[[2,4,6],[1,3,5]]
[[1,2,3,4,5,6]]