Merge Sort ist ein Sortieralgorithmus, bei dem eine bestimmte Liste in zwei Hälften geteilt, beide kleineren Listen rekursiv sortiert und zu einer sortierten Liste zusammengeführt werden. Der Grundfall der Rekursion trifft auf eine Singleton-Liste, die nicht weiter aufgeteilt werden kann, sondern per Definition bereits sortiert ist.

Die Ausführung des Algorithmus in der Liste [1,7,6,3,3,2,5]kann folgendermaßen visualisiert werden:

       [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]

Die Aufgabe

Schreiben Sie ein Programm oder eine Funktion, die eine Liste von ganzen Zahlen als Eingabe verwendet und die verschiedenen Partitionen dieser Liste visualisiert, während sie nach einem Sortieralgorithmus für das Zusammenführen sortiert werden. Dies bedeutet, dass Sie kein Diagramm wie oben ausgeben müssen, aber nur die Listen sind in Ordnung:

[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]

Darüber hinaus ist jede vernünftige Listennotation in Ordnung, daher wäre auch Folgendes eine gültige Ausgabe:

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

Schließlich liegt es an Ihnen, eine Liste in zwei kleinere Listen aufzuteilen, solange sich die Länge der beiden resultierenden Listen höchstens um eins unterscheidet. Das heißt, anstatt [3,2,4,3,7]in [3,2,4]und [3,7]aufzuteilen, können Sie auch aufteilen, indem Sie jedes Mal Elemente mit geraden und ungeraden Indizes ( [3,4,7]und [2,3]) verwenden oder die Aufteilung nach dem Zufallsprinzip vornehmen.

Das ist Code-Golf , also gewinnt der kürzeste Code in jeder Sprache, gemessen in Bytes.

Testfälle

Wie oben erwähnt, liegt das tatsächliche Format und die Möglichkeit, Listen in zwei Hälften zu teilen, bei Ihnen.

[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]

Haskell , 137 128 127 125 121 109 106 Bytes

^{(-2) + (- 4) = (- 6) Bytes dank nimi ! Wenn Sie es ändern, um alle Schritte in einer Liste zu erfassen (erneut aufgrund von nimi), werden 12 weitere Bytes gespart.}

^{Weitere 3 Bytes aufgrund von Laikoni , mit Pattern-Guard-Bindung und einer geschickten Verwendung des Listenverständnisses zum Codieren des 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

Probieren Sie es online!

Das Aufteilen der Listen in ungerade und gerade positionierte Elemente ist ein kürzerer Code als das Aufteilen in zwei aufeinanderfolgende Hälften, da wir das lengthdann nicht messen müssen.

Arbeitet, indem die Listen "gedruckt" werden, dann mit den geteilten Listen ( x >>= h) wiederholt wird, wenn tatsächlich eine Teilung durchgeführt wurde, und die sortierten Listen "gedruckt" werden; beginnend mit der einen Eingabeliste; Annahme der nicht leeren Eingabe. Und anstatt zu drucken, sammeln Sie sie einfach in einer Liste.

Die Liste, die von g[[6,5..1]]Zeile für Zeile gedruckt wird, lautet:

[[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]]

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]&

Probieren Sie es online!

Gibt ein zurück List, das die Schritte enthält.

Erläuterung

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

Teilen Sie in einer Eingabe alle auf List s, die 2 oder mehr Ganzzahlen enthalten, in zwei Hälften. Die erste Unterliste enthält die ungeradzahligen Elemente (1-indiziert) und die zweite die geradzahligen Elemente.

u=Most[... &~FixedPointList~#]

Wiederholen Sie dies, bis sich nichts mehr ändert (dh alle Unterlisten haben die Länge 1). Behalten Sie alle Zwischenergebnisse bei. Speichern Sie diese (die Listaller Schritte) in u.

Reverse@Most@u

Löschen Sie das letzte Element von uund kehren Sie es um.

... /.a:{b}:>Sort@a

Sortieren Sie aus dem obigen Ergebnis alle Vorkommen einer Liste von ganzen Zahlen.

Sauber , 228 206 168 157 140 121 104 Bytes

Erstellt die Liste der Stufen von den Enden nach innen unter Verwendung der Tatsache, dass das n-te Element vom Ende die sortierte Version von istn -ten Elements vom Anfang ist.

Idee aus dem Kommentar von JungHwan Min

import StdEnv
@u#(a,b)=splitAt(length u/2)u
=if(a>[])[[u]:[x++y\\y<- @b&x<- @a++ @a++ @a]][]++[[sort u]]

Probieren Sie es online!

Charcoal , 145 133 123 122 Bytes

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

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Immer noch um Holzkohle-Bugs herumarbeiten müssen ... Bearbeiten: 5 Bytes gespart, indem ein Double Mapals Array-Verständnis eines armen Mannes verwendet wird. 4 Bytes wurden mit gespeichert, Popum die Iteration über ein Array zu verdoppeln. 3 Bytes durch Verkettung anstelle von gespeichert Push. Es wurden 10 Byte eingespart while, indem ein besserer Golf- Zustand erreicht wurde, der auch einen Charcoal-Bug vermeidet. 1 Byte gespart, indem festgestellt wurde, dass Charcoal tatsächlich einen Filteroperator hat. Erläuterung:

≔⟦⪪Ｓ ⟧θ

Teilen Sie die Eingabe in Leerzeichen auf und verpacken Sie das Ergebnis in ein äußeres Array q.

Ｗ⊖Ｌ§θ⁰«

Wiederholen, während das erste Element von qmehr als ein Element hat. (Das erste Element von qhat aufgrund der Zweiteilung der Listen immer die meisten Elemente.)

⟦⪫Ｅθ⪫κ ¦|⟧

Drucken Sie die Elemente der Verbindung qmit Leerzeichen und vertikalen Linien. (Das Array bewirkt, dass das Ergebnis in einer eigenen Zeile gedruckt wird. Es gibt andere Möglichkeiten, dies bei gleicher Bytezahl zu erreichen.)

≔ＥＥ⊗Ｌθ§θ÷λ²✂κ﹪λ²Ｌκ²θ»

Erstellen Sie eine Liste, indem Sie jedes Element von duplizieren q, dann über diese Liste mappen und die Hälfte jeder Liste (unter Verwendung des alternativen Elementansatzes) nehmen und das Ergebnis wieder in speichern q.

⟦⪫ΦＥθ⪫ι ι|⟧

Drucken Sie die Elemente der Verbindung qmit Leerzeichen und vertikalen Linien. Momentan sind die Elemente von qentweder leere Listen oder Listen mit einzelnen Elementen. Wenn Sie sie verbinden, werden sie einfach in leere Zeichenfolgen oder ihre Elemente konvertiert. Die leeren Zeichenfolgen würden unnötige nachgestellte Zeilen hinzufügen, damit sie herausgefiltert werden. Ein Flachmann wäre allerdings golfer gewesen (so etwas wie ⟦⪫Σθ|⟧).

Ｗ⊖Ｌθ«

Wiederholen, während qmehr als ein Element hat. (Der folgende Code erfordert eine gerade Anzahl von Elementen.)

≔⮌θη≔⟦⟧θ

Kopieren qnach h, jedoch rückgängig gemacht (siehe unten) und qauf eine leere Liste zurücksetzen .

Ｗη«

Wiederholen, bis hleer ist.

≔⊟ηε

Extrahieren Sie das nächste Element von hin e. ( PopAuszüge aus dem Ende, weshalb ich umkehren muss q.)

≔⟦⟧ζ

Initialisieren Sie zauf eine leere Liste.

Ｆ⊟η«

Schleife über die Elemente des nächsten Elements von h.

≔εδ≔⟦⟧ε

Kopieren Sie eauf dund setzen Sie eauf eine leere Liste.

Ｆδ

Schlaufe über die Elemente von d.

⊞⎇‹ＩμＩλζεμ

Schieben Sie sie auf zoder eabhängig davon, ob sie kleiner als das aktuelle Element des nächsten Elements von sind h.

⊞ζλ»

Schieben Sie das aktuelle Element des nächsten Elements von hnach z.

⊞θ⁺ζε»

Verketten Sie zmit allen Elementen, die noch enthalten sind, eund verschieben Sie diese auf q. Damit ist die Zusammenführung von zwei Elementen von abgeschlossen h.

⟦⪫Ｅθ⪫κ ¦|

Drucken Sie die Elemente der Verbindung qmit Leerzeichen und vertikalen Linien.

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!

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

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.

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