[Question]
  [
[Merge sort](https://en.wikipedia.org/wiki/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](/questions/tagged/code-golf "show questions tagged '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]
```
  
[Answer]
# [Haskell](https://www.haskell.org/), ~~137~~ ~~128~~ ~~127~~ ~~125~~ ~~121~~ ~~109~~ 106 bytes
(-2)+(-4)=(-6) bytes thanks to [nimi](https://codegolf.stackexchange.com/users/34531/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](https://codegolf.stackexchange.com/users/56433/laikoni), with pattern guard binding and a clever use of list comprehension to encode the guard. 
```
import Data.List
g x|y<-x>>=h=x:[z|x/=y,z<-g y++[sort<$>x]]
h[a]=[[a]]
h x=foldr(\x[b,a]->[x:a,b])[[],[]]x
```
[Try it online!](https://tio.run/##Dcq/DoIwEIDxnae4gUFDW@OgA6GdHPUJzos5okIj/wIdroR3ryxffsPX8vL7dF1Kvp/GOcCNA5u7X0LWgGyx0uKcba2UuG5yslGtlW4gFgUu@17lToiyFpks7tkJYr9j954PT8FaMWmHUrKq6YhICokk9ewH2/P0eME0@yFADg3iVV2MOROlPw "Haskell – 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 >>= 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]]
```
[Answer]
# [Wolfram Language (Mathematica)](https://www.wolfram.com/wolframscript/), ~~146~~ ~~127~~ ~~111~~ 102 bytes
```
Join[u=Most[#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&~FixedPointList~#],Reverse@Most@u/.a:{b}:>Sort@a]&
```
[Try it online!](https://tio.run/##y00syUjNTSzJTE78n2b73ys/My@61NY3v7gkWllfL9GqOl4nyTY@3jOvJDU9tajWyi4kMTvVpSi/IDpRxxoIjGLV6twyK1JTAoA6S3wyi0vqlGN1glLLUouKUx1A5jiUgs1JAuoNzi8qcUiMVfsfUARUrO@QFs3FVW2oY65jpmMMhEY6prVcXLH/AQ "Wolfram Language (Mathematica) – Try It Online")
Returns a `List` that contains the steps.
## Explanation
```
#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&
```
In an input, split all `List`s containing 2 or more integers in half. The first sublist has the odd-indexed elements (1-indexed), and the second one has the even-indexed elements.
```
u=Most[... &~FixedPointList~#]
```
Repeat that until nothing changes (i.e. all sublists are length-1). Keep all intermediate results. Store this (the `List` of all steps) in `u`.
```
Reverse@Most@u
```
Drop the last element of `u` and reverse it.
```
... /.a:{b}:>Sort@a
```
From the result above, sort all occurrences of a list of integers.
[Answer]
# [Clean](https://clean.cs.ru.nl), ~~228~~ ~~206~~ ~~168~~ ~~157~~ ~~140~~ ~~121~~ 104 bytes
Builds the list of stages from the ends inwards, using the fact that the `n`-th element from the end is the sorted version of the `n`-th element from the beginning.
*Idea from [JungHwan Min's comment](https://codegolf.stackexchange.com/questions/150675/visualize-merge-sort/150686#comment368300_150675)*
```
import StdEnv
@u#(a,b)=splitAt(length u/2)u
=if(a>[])[[u]:[x++y\\y<- @b&x<- @a++ @a++ @a]][]++[[sort u]]
```
[Try it online!](https://tio.run/##NYy9CsIwFEb3PkVAkJakiBUVxEoFHQS3jrcZbn8NJGkxibQvb2wH@eCcM32VbFB71ddONkSh0F6ooX9bktv6rj9B5lYhsjJKzSCFvdpQNrqzL@I2SeSCVLQhXoBHAI6fYKR0KorpHJOsXI@LkNI/OAdOKYBZ3h3nPrc4V0oyAlt2ZAe2m5ewPfffqpXYGR8/nv42aVSiMj8 "Clean – Try It Online")
[Answer]
# [Charcoal](https://github.com/somebody1234/Charcoal), ~~145~~ ~~133~~ ~~123~~ 122 bytes
```
≔⟦⪪Ｓ ⟧θＷ⊖Ｌ§θ⁰«⟦⪫Ｅθ⪫κ ¦|⟧≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»⟦⪫ΦＥθ⪫ι ι|⟧Ｗ⊖Ｌθ«≔⮌θη≔⟦⟧θＷη«≔⊟ηε≔⟦⟧ζＦ⊟η«≔εδ≔⟦⟧εＦδ⊞⎇‹ＩμＩλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Ｅθ⪫κ ¦|
```
[Try it online!](https://tio.run/##hVHLTsMwEDw3X7HqyZaMBEXAgROiQiqiUkS5VRxCsjRWXSexnQKFfHvwq8IcEIkSObszszObsi5U2RRiHG@05htJ1qtWcEMWsu3NyiguN4QymMKUPjPo6HX2VnOBQOZYKtyhNFiRB5QbU5Mbs5AVvpOOwSm1F3xmk9wqGLK@b7gky6J1PX/eBk37/rLKVnYS5zuQe@ZN/yJ@tDtqscmAhTRzvucVEsFgRl13JXiJTnjZVL1oQoNBFNhSjwsZhiz1dceFQfXLHj/a44nFv5N3MW3M8Ih7VBptmUGdZFvHFU6iUu1Jx27etLbCAB0ipRx84bVREDGBdoQgg8ojUk4QCaSKQt7rmjyhkoX6sKa1JreFNmRnx/mDcJs5OBqDXaB6ii0J/zlksWI3lIteEw92reHfn5yscBjHM7iCSzi39wwusvFkL74B "Charcoal – Try It Online") Link is to verbose version of code. ~~Still having to work around Charcoal bugs...~~ Edit: Saved 5 bytes by using a double `Map` as a poor man's array comprehension. Saved 4 bytes by using `Pop` to double iterate over an array. Saved 3 bytes by using concatenation instead of `Push`. Saved 10 bytes by coming up with a golfier `while` condition that also avoids a Charcoal bug. Saved 1 byte by discovering that Charcoal does indeed have a filter operator. Explanation:
```
≔⟦⪪Ｓ ⟧θ
```
Split the input on spaces, and then wrap the result in an outer array, saving that to `q`.
```
Ｗ⊖Ｌ§θ⁰«
```
Repeat while the first element of `q` has more than one element. (The first element of `q` always has the most elements because of the way the lists are divided into two.)
```
⟦⪫Ｅθ⪫κ ¦|⟧
```
Print the elements of `q` joined with spaces and vertical lines. (The array causes the result to print on its own line. There are other ways of achieving this for the same byte count.)
```
≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»
```
Create a list by duplicating each element of `q`, then map over that list and take half of each list (using the alternate element approach), saving the result back in `q`.
```
⟦⪫ΦＥθ⪫ι ι|⟧
```
Print the elements of `q` joined with spaces and vertical lines. Actually, at this point the elements of `q` are either empty or single-element lists, so joining them just converts them to empty strings or their elements. The empty strings would add unnecessary trailing lines so they are filtered out. A flatten operator would have been golfier though (something like `⟦⪫Σθ|⟧`).
```
Ｗ⊖Ｌθ«
```
Repeat while `q` has more than one element. (The following code requires an even number of elements.)
```
≔⮌θη≔⟦⟧θ
```
Copy `q` to `h`, but reversed (see below), and reset `q` to an empty list.
```
Ｗη«
```
Repeat until `h` is empty.
```
≔⊟ηε
```
Extract the next element of `h` into `e`. (`Pop` extracts from the end, which is why I have to reverse `q`.)
```
≔⟦⟧ζ
```
Initialise `z` to an empty list.
```
Ｆ⊟η«
```
Loop over the elements of the next element of `h`.
```
≔εδ≔⟦⟧ε
```
Copy `e` to `d` and reset `e` to an empty list.
```
Ｆδ
```
Loop over the elements of `d`.
```
⊞⎇‹ＩμＩλζεμ
```
Push them to `z` or `e` depending on whether they are smaller than the current element of the next element of `h`.
```
⊞ζλ»
```
Push the current element of the next element of `h` to `z`.
```
⊞θ⁺ζε»
```
Concatenate `z` with any elements remaining in `e` and push that to `q`. This completes the merge of two elements of `h`.
```
⟦⪫Ｅθ⪫κ ¦|
```
Print the elements of `q` joined with spaces and vertical lines.
[Answer]
# [Python 2](https://docs.python.org/2/), ~~145~~ 144 bytes
Idea from [JungHwan Min's comment](https://codegolf.stackexchange.com/questions/150675/visualize-merge-sort/150686#comment368300_150675)  
-1 byte thanks to Jonathan Frech  
```
p=input()
l=[[p]]
i=0
while 2**i<len(p):l[i+1:i+1]=[sum([[x[1::2],x[::2]][len(x)<2:]for x in l[i]],[]),map(sorted,l[i])];i+=1
for s in l:print s
```
[Try it online!](https://tio.run/##HYvBCsMgEETvfoVHTfZQLW3Bxi9Z9lBoShaskWio/XobyzAMPN6kb1nWaFtLnmPai9IieMREJNifxGfhMEs7DDyFOaqkXUAejTtKHvP@VogVjXOWoGIfwi5WPVlHr3WTVXKUx4kIkDS8H0nldSvzEzrUdOfRG9HN/Ddd2jgWmVtDAze4wvmIhQv9AA "Python 2 – Try It Online")
[Answer]
# [Husk](https://github.com/barbuz/Husk), 14 bytes
```
S+ȯ†O↔hUmfL¡ṁ½
```
Takes an array containing a single array.
[Try it online!](https://tio.run/##AS8A0P9odXNr//9TK8iv4oCgT@KGlGhVbWZMwqHhuYHCvf///1tbNiw1LDQsMywyLDFdXQ "Husk – Try It Online")
## Explanation
```
S+ȯ†O↔hUmfL¡ṁ½  Implicit input, say A = [[4,17,32,1]].
           ¡    Iterate this function on A:
            ṁ½   Split each array in two, concatenate results: [[4,17],[32,1]]
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[],[17],[],[32],[],[1],[]],
                           ...
        mfL     Map filter by length, removing empty arrays.
                Result is [[[4,17,32,1]],
                           [[4,17],[32,1]],
                           [[4],[17],[32],[1]],
                           [[4],[17],[32],[1]],
                           ...
       U        Longest prefix of unique elements:
                       P = [[[4,17,32,1]],[[4,17],[32,1]],[[4],[17],[32],[1]]]
      h         Remove last element: [[[4,17,32,1]],[[4,17],[32,1]]]
     ↔          Reverse: [[[4,17],[32,1]],[[4,17,32,1]]]
   †O           Sort each inner array: [[[4,17],[1,32]],[[1,4,17,32]]]
S+ȯ             Concatenate to P:
                           [[[4,17,32,1]],
                            [[4,17],[32,1]],
                            [[4],[17],[32],[1]],
                            [[4,17],[1,32]],
                            [[1,4,17,32]]]
                Implicitly print.
```
The built-in `½` takes an array and splits it at the middle.
If its length is odd, the first part is longer by one element.
A singleton array `[a]` results in `[[a],[]]` and an empty array `[]` gives `[[],[]]`, so it's necessary to remove the empty arrays before applying `U`.
[Answer]
## JavaScript (ES6), 145 bytes
```
f=a=>a.join`|`+(a[0][1]?`
${f([].concat(...a.map(b=>b[1]?[b.slice(0,c=-b.length/2),b.slice(c)]:[b])))}
`+a.map(b=>b.sort((x,y)=>x-y)).join`|`:``)
```
Takes input as an array within an array, i.e. `f([[6,5,4,3,2,1]])`. Works by generating the first and last lines of the output, then splitting and calling itself again, until every sub-array has length 1. Here's a basic demonstration of how it works:
```
f([[6,5,4,3,2,1]]):
  6,5,4,3,2,1
  f([[6,5,4],[3,2,1]]):
    6,5,4|3,2,1
    f([[6,5],[4],[3,2],[1]]):
      6,5|4|3,2|1
      f([[6],[5],[4],[3],[2],[1]]):
        6|5|4|3|2|1
      end f
      5,6|4|2,3|1
    end f
    4,5,6|1,2,3
  end f
  1,2,3,4,5,6
end f
```
[Answer]
# [Stax](https://github.com/tomtheisen/stax), ~~116(÷3>)~~ ~~38~~ 29 [bytes](https://github.com/tomtheisen/stax/blob/master/docs/packed.md#packed-stax)CP437
-9 bytes per comment by @recursive. Now the input is given as a singleton whose only element is an array of the numbers to be sorted.
```
ƒ3s}óºE/ßB╢↕êb∩áαπüµrL╞¶è,te+
```
[Try it online!](https://staxlang.xyz/#c=%C6%923s%7D%C3%B3%C2%BAE%2F%C3%9FB%E2%95%A2%E2%86%95%C3%AAb%E2%88%A9%C3%A1%CE%B1%CF%80%C3%BC%C2%B5rL%E2%95%9E%C2%B6%C3%A8%2Cte%2B&i=%5B%5B10%2C2%5D%5D%0A%5B%5B4%2C17%2C1%2C32%5D%5D%0A%5B%5B6%2C5%2C4%2C3%2C2%2C1%5D%5D&a=1&m=2)
Unpacked version with 35 bytes:
```
{c{Jm'|*Pc{2Mm:f{fc{Dm$wW{{eoJm'|*P
```
## Explanation
The code can be splitted to two parts. The first part visualizes splitting and the second visualizes merging.
Code for visualizing splitting:
```
{                      w    Do the following while the block generates a true value
 c                          Copy current nested array for printing
  {Jm                       Use spaces to join elements in each part
     '|*                    And join different parts with vertical bar 
        P                   Pop and print
         c                  Copy current nested array for splitting
          {2Mm              Separate each element of the array to two smaller parts with almost the same size
                                That is, if the number of elements is even, partition it evenly.
                                Otherwise, the first part will have one more element than the second.
              :f            Flatten the array once
                {f          Remove elements that are empty arrays
                  c         Copy the result for checking 
                   {Dm$     Is the array solely composed of singletons?
                            If yes, ends the loop.
```
The code for visualizing merging:
```
W              Execute the rest of the program until the stack is empty
 {{eoJm        For each part, sort by numeric value, then join with space
       '|*     Join the parts with vertical bar
          P    Pop and print the result
```
## Old version, actually building the nested list structure.
```
{{cc0+=!{x!}Mm',*:}}Xd;%v:2^^{;s~{c^;<~sc%v,*{2M{s^y!svsm}M}YZ!x!Q,dmU@e;%v:2^{;%v:2^-N~0{c;={scc0+=Cc%v!C:f{o}{scc0+=C{s^y!svsm}?}Y!cx!P,dcm
```
`cc0+=` is used thrice in the code to check whether the top of stack is a scalar or an array.
`{{cc0+=!{x!}Mm',*:}}X` builds a block that recursively calls itself to output a nested array of numbers properly. (Default output in Stax vectorizes a nested array before printing).
```
{                  }X    Store the code block in X
 {           m           Map each element in the list with block
  cc                     Make two copies of the element
    0+                   + 0. If the element is a scalar, nothing will change
                              If the element is an array, the element 0 will be appended
      =!{  }M            If the element has changed after the `0+` operation
                             Which means it is an array
         x!              Recursively execute the whole code block on the element
                         
              ',*        Join the mapped elements with comma
                 :}      Bracerizes the final result
```
There are two other blocks that performs the splitting and the merging, respectively. They are too verbose and I don't care to explain (there are a little bit more information in the historical version of this post but don't expect too much).
]