Visualize Merge Sort

Question

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]

Answer 1

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<-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!

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 2

Wolfram Language (Mathematica), 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!

Returns a List that contains the steps.

Explanation

#/.a:{_,b=__Integer}:>TakeDrop[a,;;;;2]&

In an input, split all Lists 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 3

Clean, 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

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!

Answer 4

Charcoal, 145 133 123 122 bytes

≔⟦⪪Ｓ ⟧θＷ⊖Ｌ§θ⁰«⟦⪫Ｅθ⪫κ ¦|⟧≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»⟦⪫ΦＥθ⪫ι ι|⟧Ｗ⊖Ｌθ«≔⮌θη≔⟦⟧θＷη«≔⊟ηε≔⟦⟧ζＦ⊟η«≔εδ≔⟦⟧εＦδ⊞⎇‹ＩμＩλζεμ⊞ζλ»⊞θ⁺ζε»⟦⪫Ｅθ⪫κ ¦|

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 5

Python 2, 145 144 bytes

^{Idea from JungHwan Min's comment
-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!

Answer 6

Husk, 14 bytes

S+ȯ†O↔hUmfL¡ṁ½

Takes an array containing a single array. 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 7

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 8

Stax, 116(÷3>) 38 29 bytes^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!

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).