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] <- 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]
[[1,2],[3],[4,5],[6]]
stage is actually the correct solution, as merge sort is working recursively. That is if we start with[1,2,3,4,5,6]
and split it into[1,2,3]
and[4,5,6]
, then those lists are independently processed until they are merged in the final step. \$\endgroup\$[3]
and[2,1]
, then those are on different branches, so we can't merge[3]
and[2]
after[2,1]
is split into[2]
and[1]
. \$\endgroup\$