<!-- canonical: https://efficientnewlanguage.org/eml-p/projects/P045-sorting-visualizer/ | updated: 2026-10-10 -->

# P045 Sorting visualizer

A list of up to 12 numbers sorted step by step by bubble sort, insertion sort, merge sort or counting sort - every pass, insertion or merge shown with the part already in place - with the comparisons and moves each one took, or all four side by side on the same list.

EML-P project `projects/sorting-visualizer` in the EML language repo: 2 module(s), entry `main.eml`, terminal UI. There, `eml project run projects/sorting-visualizer` runs it and `eml project verify projects/sorting-visualizer` replays every session under CPython (two hash seeds) and in the interpreter; the site build replays every session in the interpreter again and publishes a session only if its screen matches.

Built on verified corpus cases: bubble-sort (https://efficientnewlanguage.org/cases/051-bubble-sort/), insertion-sort (https://efficientnewlanguage.org/cases/054-insertion-sort/), merge-sort (https://efficientnewlanguage.org/cases/074-merge-sort/), counting-sort (https://efficientnewlanguage.org/cases/067-counting-sort/).

## Sessions

### bad-input - interpreter: byte-equal to the golden

Input:

```text
0
x
1

1
5
1
1 2 x
1
100 2
1
0 1 2 3 4 5 6 7 8 9 10 11 12
1
-1 5
1
7,7
2
3
4
5
6
7
```

Screen:

```text
== Sorting visualizer ==
Watch four sorts work on the same list, step by step.
The list: 29  3 17 42  8  3 25 11

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 0
Pick a number from 1 to 7.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> x
Pick a number from 1 to 7.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 
Cancelled.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 5
Give at least 2 numbers. The list stays as it was.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 1 2 x
Not a number from 0 to 99: x. The list stays as it was.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 100 2
Not a number from 0 to 99: 100. The list stays as it was.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 0 1 2 3 4 5 6 7 8 9 10 11 12
That is 13 numbers; the most is 12. The list stays as it was.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> -1 5
Not a number from 0 to 99: -1. The list stays as it was.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 7,7
The list:  7  7

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 2
bubble sort of  7  7
  pass 1: 0 swaps     7  7
Sorted:  7  7 - 1 comparison, 0 swaps.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 3
insertion sort of  7  7
  insert 7: 0 shifted     7  7
Sorted:  7  7 - 1 comparison, 0 shifts.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 4
merge sort of  7  7
  merge [7] + [7]
    ->  7  7
Sorted:  7  7 - 1 comparison, 2 values written.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 5
counting sort of  7  7
  counts: 7 x2
    ->  7  7
Sorted:  7  7 - 0 comparisons, 2 values written.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 6
All four on  7  7:
               comparisons  moves
  bubble                 1      0  (swaps)
  insertion              1      0  (shifts)
  merge                  1      2  (values written)
  counting               0      2  (values written)
Counting sort compares nothing: it only works because the values are small whole numbers.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 7
Bye.
```

### basic - interpreter: byte-equal to the golden

Input:

```text
2
3
4
5
6
1
9 8 7 6 5 4 3 2 1
2
1
1 2 3 4 5 6
2
3
6
7
```

Screen:

```text
== Sorting visualizer ==
Watch four sorts work on the same list, step by step.
The list: 29  3 17 42  8  3 25 11

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 2
bubble sort of 29  3 17 42  8  3 25 11
  pass 1: 6 swaps     3 17 29  8  3 25 11 | 42
  pass 2: 4 swaps     3 17  8  3 25 11 | 29 42
  pass 3: 3 swaps     3  8  3 17 11 | 25 29 42
  pass 4: 2 swaps     3  3  8 11 | 17 25 29 42
  pass 5: 0 swaps     3  3  8 11 17 25 29 42
Sorted:  3  3  8 11 17 25 29 42 - 25 comparisons, 15 swaps.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 3
insertion sort of 29  3 17 42  8  3 25 11
  insert 3: 1 shifted     3 29 | 17 42  8  3 25 11
  insert 17: 1 shifted    3 17 29 | 42  8  3 25 11
  insert 42: 0 shifted    3 17 29 42 |  8  3 25 11
  insert 8: 3 shifted     3  8 17 29 42 |  3 25 11
  insert 3: 4 shifted     3  3  8 17 29 42 | 25 11
  insert 25: 2 shifted    3  3  8 17 25 29 42 | 11
  insert 11: 4 shifted    3  3  8 11 17 25 29 42
Sorted:  3  3  8 11 17 25 29 42 - 21 comparisons, 15 shifts.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 4
merge sort of 29  3 17 42  8  3 25 11
  merge [29] + [3]
    ->  3 29
  merge [17] + [42]
    -> 17 42
  merge [3 29] + [17 42]
    ->  3 17 29 42
  merge [8] + [3]
    ->  3  8
  merge [25] + [11]
    -> 11 25
  merge [3 8] + [11 25]
    ->  3  8 11 25
  merge [3 17 29 42] + [3 8 11 25]
    ->  3  3  8 11 17 25 29 42
Sorted:  3  3  8 11 17 25 29 42 - 15 comparisons, 24 values written.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 5
counting sort of 29  3 17 42  8  3 25 11
  counts: 3 x2, 8 x1, 11 x1, 17 x1, 25 x1, 29 x1, 42 x1
    ->  3  3  8 11 17 25 29 42
Sorted:  3  3  8 11 17 25 29 42 - 0 comparisons, 8 values written.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 6
All four on 29  3 17 42  8  3 25 11:
               comparisons  moves
  bubble                25     15  (swaps)
  insertion             21     15  (shifts)
  merge                 15     24  (values written)
  counting               0      8  (values written)
Counting sort compares nothing: it only works because the values are small whole numbers.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 9 8 7 6 5 4 3 2 1
The list:  9  8  7  6  5  4  3  2  1

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 2
bubble sort of  9  8  7  6  5  4  3  2  1
  pass 1: 8 swaps     8  7  6  5  4  3  2  1 |  9
  pass 2: 7 swaps     7  6  5  4  3  2  1 |  8  9
  pass 3: 6 swaps     6  5  4  3  2  1 |  7  8  9
  pass 4: 5 swaps     5  4  3  2  1 |  6  7  8  9
  pass 5: 4 swaps     4  3  2  1 |  5  6  7  8  9
  pass 6: 3 swaps     3  2  1 |  4  5  6  7  8  9
  pass 7: 2 swaps     2  1 |  3  4  5  6  7  8  9
  pass 8: 1 swap      1  2  3  4  5  6  7  8  9
Sorted:  1  2  3  4  5  6  7  8  9 - 36 comparisons, 36 swaps.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 1
numbers (up to 12, from 0 to 99)> 1 2 3 4 5 6
The list:  1  2  3  4  5  6

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 2
bubble sort of  1  2  3  4  5  6
  pass 1: 0 swaps     1  2  3  4  5  6
Sorted:  1  2  3  4  5  6 - 5 comparisons, 0 swaps.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 3
insertion sort of  1  2  3  4  5  6
  insert 2: 0 shifted     1  2 |  3  4  5  6
  insert 3: 0 shifted     1  2  3 |  4  5  6
  insert 4: 0 shifted     1  2  3  4 |  5  6
  insert 5: 0 shifted     1  2  3  4  5 |  6
  insert 6: 0 shifted     1  2  3  4  5  6
Sorted:  1  2  3  4  5  6 - 5 comparisons, 0 shifts.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 6
All four on  1  2  3  4  5  6:
               comparisons  moves
  bubble                 5      0  (swaps)
  insertion              5      0  (shifts)
  merge                  7     16  (values written)
  counting               0      6  (values written)
Counting sort compares nothing: it only works because the values are small whole numbers.

1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit
choice> 7
Bye.
```

## Modules

### main.eml

```eml
# P045 sorting visualizer: a list of up to 12 numbers from 0 to 99, sorted
# step by step by bubble sort, insertion sort, merge sort or counting sort -
# each step shown, with the comparisons and moves it took - or all four side
# by side on the same list.
import sorts

12 => most_values

def trim(s):
    0 => i
    len(s) => j
    while i < j and s[i] == " ":
        i + 1 => i
    while j > i and s[j - 1] == " ":
        j - 1 => j
    return s[i:j]

def words(s):
    [] => out
    "" => word
    for c in s + " ":
        if c == " " or c == ",":
            if word != "":
                out + [word] => out
            "" => word
        else:
            word + c => word
    return out

def number(s):
    if s == "" or len(s) > 2:
        return -1
    0 => n
    for c in s:
        if not (c in "0123456789"):
            return -1
        n * 10 + int(c) => n
    return n

def right(s, width):
    while len(s) < width:
        " " + s => s
    return s

def pad(s, width):
    while len(s) < width:
        s + " " => s
    return s

def row(xs, done, from_right):
    # The list with a bar between the part in place and the rest: in place
    # at the end for bubble sort, at the start for insertion sort.
    "" => out
    len(xs) => n
    for i in [0:n - 1]:
        if from_right and i == n - done and done < n:
            out + " |" => out
        out + " " + right(str(xs[i]), 2) => out
        if not from_right and i == done - 1 and done < n:
            out + " |" => out
    return out

def counted(n, words):
    if n == 1:
        return "1 " + words[0]
    return str(n) + " " + words[1]

def run(xs, which):
    ["bubble", "insertion", "merge", "counting"] => names
    if which == 0:
        sorts.bubble(xs) => r
    elif which == 1:
        sorts.insertion(xs) => r
    elif which == 2:
        sorts.merge(xs) => r
    else:
        sorts.counting(xs) => r
    (names[which] + " sort of" + row(xs, 0, True)) ^0
    for st in r[1]:
        if which == 0:
            ("  " + pad(st[0], 18) + row(st[1], st[2], True)) ^0
        elif which == 1:
            ("  " + pad(st[0], 22) + row(st[1], st[2], False)) ^0
        else:
            ("  " + st[0]) ^0
            ("    ->" + row(st[1], st[2], True)) ^0
    [["swap", "swaps"], ["shift", "shifts"], ["value written", "values written"], ["value written", "values written"]] => what
    ("Sorted:" + row(r[0], len(r[0]), True) + " - " + counted(r[2], ["comparison", "comparisons"]) + ", " + counted(r[3], what[which]) + ".") ^0
    return r

def compare(xs):
    ("All four on" + row(xs, 0, True) + ":") ^0
    "               comparisons  moves" ^0
    ["bubble", "insertion", "merge", "counting"] => names
    ["swaps", "shifts", "values written", "values written"] => what
    for k in [0:3]:
        if k == 0:
            sorts.bubble(xs) => r
        elif k == 1:
            sorts.insertion(xs) => r
        elif k == 2:
            sorts.merge(xs) => r
        else:
            sorts.counting(xs) => r
        ("  " + pad(names[k], 12) + right(str(r[2]), 12) + right(str(r[3]), 7) + "  (" + what[k] + ")") ^0
    "Counting sort compares nothing: it only works because the values are small whole numbers." ^0

def ask_list(xs):
    trim(input("numbers (up to 12, from 0 to 99)> ")) => answer
    if answer == "":
        "Cancelled." ^0
        return xs
    [] => out
    for w in words(answer):
        number(w) => n
        if n < 0:
            ("Not a number from 0 to 99: " + w + ". The list stays as it was.") ^0
            return xs
        out + [n] => out
    if len(out) > most_values:
        ("That is " + str(len(out)) + " numbers; the most is " + str(most_values) + ". The list stays as it was.") ^0
        return xs
    if len(out) < 2:
        "Give at least 2 numbers. The list stays as it was." ^0
        return xs
    ("The list:" + row(out, 0, True)) ^0
    return out

"== Sorting visualizer ==" ^0
"Watch four sorts work on the same list, step by step." ^0
[29, 3, 17, 42, 8, 3, 25, 11] => xs
("The list:" + row(xs, 0, True)) ^0
True => running
while running:
    "" ^0
    "1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit" ^0
    trim(input("choice> ")) => choice
    if choice == "1":
        ask_list(xs) => xs
    elif choice == "2" or choice == "3" or choice == "4" or choice == "5":
        run(xs, int(choice) - 2)
    elif choice == "6":
        compare(xs)
    elif choice == "7":
        False => running
    else:
        "Pick a number from 1 to 7." ^0
"Bye." ^0
```

Python projection of main.eml:

```python
import sorts
most_values = 12

def trim(s):
    i = 0
    j = len(s)
    while i < j and s[i] == " ":
        i = i + 1
    while j > i and s[j - 1] == " ":
        j = j - 1
    return s[i:j]

def words(s):
    out = []
    word = ""
    for c in s + " ":
        if c == " " or c == ",":
            if word != "":
                out = out + [word]
            word = ""
        else:
            word = word + c
    return out

def number(s):
    if s == "" or len(s) > 2:
        return -1
    n = 0
    for c in s:
        if not c in "0123456789":
            return -1
        n = n * 10 + int(c)
    return n

def right(s, width):
    while len(s) < width:
        s = " " + s
    return s

def pad(s, width):
    while len(s) < width:
        s = s + " "
    return s

def row(xs, done, from_right):
    out = ""
    n = len(xs)
    for i in range(0, n):
        if from_right and i == n - done and done < n:
            out = out + " |"
        out = out + " " + right(str(xs[i]), 2)
        if not from_right and i == done - 1 and done < n:
            out = out + " |"
    return out

def counted(n, words):
    if n == 1:
        return "1 " + words[0]
    return str(n) + " " + words[1]

def run(xs, which):
    names = ["bubble", "insertion", "merge", "counting"]
    if which == 0:
        r = sorts.bubble(xs)
    elif which == 1:
        r = sorts.insertion(xs)
    elif which == 2:
        r = sorts.merge(xs)
    else:
        r = sorts.counting(xs)
    print(names[which] + " sort of" + row(xs, 0, True))
    for st in r[1]:
        if which == 0:
            print("  " + pad(st[0], 18) + row(st[1], st[2], True))
        elif which == 1:
            print("  " + pad(st[0], 22) + row(st[1], st[2], False))
        else:
            print("  " + st[0])
            print("    ->" + row(st[1], st[2], True))
    what = [["swap", "swaps"], ["shift", "shifts"], ["value written", "values written"], ["value written", "values written"]]
    print("Sorted:" + row(r[0], len(r[0]), True) + " - " + counted(r[2], ["comparison", "comparisons"]) + ", " + counted(r[3], what[which]) + ".")
    return r

def compare(xs):
    print("All four on" + row(xs, 0, True) + ":")
    print("               comparisons  moves")
    names = ["bubble", "insertion", "merge", "counting"]
    what = ["swaps", "shifts", "values written", "values written"]
    for k in range(0, 4):
        if k == 0:
            r = sorts.bubble(xs)
        elif k == 1:
            r = sorts.insertion(xs)
        elif k == 2:
            r = sorts.merge(xs)
        else:
            r = sorts.counting(xs)
        print("  " + pad(names[k], 12) + right(str(r[2]), 12) + right(str(r[3]), 7) + "  (" + what[k] + ")")
    print("Counting sort compares nothing: it only works because the values are small whole numbers.")

def ask_list(xs):
    answer = trim(input("numbers (up to 12, from 0 to 99)> "))
    if answer == "":
        print("Cancelled.")
        return xs
    out = []
    for w in words(answer):
        n = number(w)
        if n < 0:
            print("Not a number from 0 to 99: " + w + ". The list stays as it was.")
            return xs
        out = out + [n]
    if len(out) > most_values:
        print("That is " + str(len(out)) + " numbers; the most is " + str(most_values) + ". The list stays as it was.")
        return xs
    if len(out) < 2:
        print("Give at least 2 numbers. The list stays as it was.")
        return xs
    print("The list:" + row(out, 0, True))
    return out

print("== Sorting visualizer ==")
print("Watch four sorts work on the same list, step by step.")
xs = [29, 3, 17, 42, 8, 3, 25, 11]
print("The list:" + row(xs, 0, True))
running = True
while running:
    print("")
    print("1) new list  2) bubble  3) insertion  4) merge  5) counting  6) compare all  7) quit")
    choice = trim(input("choice> "))
    if choice == "1":
        xs = ask_list(xs)
    elif choice == "2" or choice == "3" or choice == "4" or choice == "5":
        run(xs, int(choice) - 2)
    elif choice == "6":
        compare(xs)
    elif choice == "7":
        running = False
    else:
        print("Pick a number from 1 to 7.")
print("Bye.")
```

### sorts.eml

```eml
# P045 sorting visualizer - four sorts that report what they do. Each one
# returns [sorted list, steps, comparisons, moves], where every step is
# [label, the list at that moment, how much of it is in place] and the
# counting rules are:
#   bubble    - a comparison of two neighbours; a move is a swap
#   insertion - a comparison with the value being inserted; a move is a
#               value shifted one place to the right
#   merge     - a comparison of the two front values; a move is a value
#               written into the merged list
#   counting  - no comparisons; a move is a value written out

def bubble(xs):
    # The corpus case bubble-sort, with the early stop: a pass without a
    # swap means the list is sorted.
    xs[0:len(xs)] => a
    len(a) => n
    [] => steps
    0 => comps
    0 => moves
    1 => p
    True => going
    while going and p < n:
        0 => swaps
        for i in [0:n - 1 - p]:
            comps + 1 => comps
            if a[i] > a[i + 1]:
                a[i] => t
                a[i + 1] => a[i]
                t => a[i + 1]
                swaps + 1 => swaps
        moves + swaps => moves
        # after pass p the last p values are in place - all of them once a
        # pass swaps nothing
        p => placed
        if swaps == 0 or p == n - 1:
            n => placed
        steps + [["pass " + str(p) + ": " + plural(swaps, "swap"), a[0:n], placed]] => steps
        if swaps == 0:
            False => going
        p + 1 => p
    return [a, steps, comps, moves]

def insertion(xs):
    # The corpus case insertion-sort: each value slides left past the larger
    # ones before it.
    xs[0:len(xs)] => a
    len(a) => n
    [] => steps
    0 => comps
    0 => moves
    for i in [1:n - 1]:
        a[i] => cur
        i - 1 => j
        0 => shifted
        True => going
        while going and j >= 0:
            comps + 1 => comps
            if a[j] > cur:
                a[j] => a[j + 1]
                shifted + 1 => shifted
                j - 1 => j
            else:
                False => going
        cur => a[j + 1]
        moves + shifted => moves
        steps + [["insert " + str(cur) + ": " + str(shifted) + " shifted", a[0:n], i + 1]] => steps
    return [a, steps, comps, moves]

def merged(left, right, counts):
    # The merge step: take the smaller front value each time; on a tie the
    # left one first, which keeps equal values in order. counts holds
    # [comparisons, moves] and is updated.
    [] => out
    0 => i
    0 => j
    while i < len(left) and j < len(right):
        counts[0] + 1 => counts[0]
        if right[j] < left[i]:
            out + [right[j]] => out
            j + 1 => j
        else:
            out + [left[i]] => out
            i + 1 => i
    out + left[i:len(left)] + right[j:len(right)] => out
    counts[1] + len(out) => counts[1]
    return out

def merge_steps(xs, counts, steps):
    # The corpus case merge-sort: halves, each sorted the same way, then
    # merged. Every merge becomes a step, added to steps[0].
    len(xs) => n
    if n <= 1:
        return xs
    int(n / 2) => mid
    merge_steps(xs[0:mid], counts, steps) => left
    merge_steps(xs[mid:n], counts, steps) => right
    merged(left, right, counts) => out
    steps[0] + [["merge " + numbers(left) + " + " + numbers(right), out, len(out)]] => steps[0]
    return out

def merge(xs):
    [0, 0] => counts
    [[]] => steps
    merge_steps(xs, counts, steps) => out
    return [out, steps[0], counts[0], counts[1]]

def counting(xs):
    # The corpus case counting-sort: count each value from 0 to 99, then
    # write each value out as often as it was counted.
    [0] * 100 => counts
    for x in xs:
        counts[x] + 1 => counts[x]
    "" => seen
    for v in [0:99]:
        if counts[v] > 0:
            if seen != "":
                seen + ", " => seen
            seen + str(v) + " x" + str(counts[v]) => seen
    [] => out
    for v in [0:99]:
        for k in [1:counts[v]]:
            out + [v] => out
    return [out, [["counts: " + seen, out, len(out)]], 0, len(out)]

def plural(n, word):
    if n == 1:
        return "1 " + word
    return str(n) + " " + word + "s"

def numbers(xs):
    "" => out
    for x in xs:
        if out != "":
            out + " " => out
        out + str(x) => out
    return "[" + out + "]"
```

Python projection of sorts.eml:

```python
def bubble(xs):
    a = xs[0:len(xs)]
    n = len(a)
    steps = []
    comps = 0
    moves = 0
    p = 1
    going = True
    while going and p < n:
        swaps = 0
        for i in range(0, n - 1 - p+1):
            comps = comps + 1
            if a[i] > a[i + 1]:
                t = a[i]
                a[i] = a[i + 1]
                a[i + 1] = t
                swaps = swaps + 1
        moves = moves + swaps
        placed = p
        if swaps == 0 or p == n - 1:
            placed = n
        steps = steps + [["pass " + str(p) + ": " + plural(swaps, "swap"), a[0:n], placed]]
        if swaps == 0:
            going = False
        p = p + 1
    return [a, steps, comps, moves]

def insertion(xs):
    a = xs[0:len(xs)]
    n = len(a)
    steps = []
    comps = 0
    moves = 0
    for i in range(1, n):
        cur = a[i]
        j = i - 1
        shifted = 0
        going = True
        while going and j >= 0:
            comps = comps + 1
            if a[j] > cur:
                a[j + 1] = a[j]
                shifted = shifted + 1
                j = j - 1
            else:
                going = False
        a[j + 1] = cur
        moves = moves + shifted
        steps = steps + [["insert " + str(cur) + ": " + str(shifted) + " shifted", a[0:n], i + 1]]
    return [a, steps, comps, moves]

def merged(left, right, counts):
    out = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        counts[0] = counts[0] + 1
        if right[j] < left[i]:
            out = out + [right[j]]
            j = j + 1
        else:
            out = out + [left[i]]
            i = i + 1
    out = out + left[i:len(left)] + right[j:len(right)]
    counts[1] = counts[1] + len(out)
    return out

def merge_steps(xs, counts, steps):
    n = len(xs)
    if n <= 1:
        return xs
    mid = int(n / 2)
    left = merge_steps(xs[0:mid], counts, steps)
    right = merge_steps(xs[mid:n], counts, steps)
    out = merged(left, right, counts)
    steps[0] = steps[0] + [["merge " + numbers(left) + " + " + numbers(right), out, len(out)]]
    return out

def merge(xs):
    counts = [0, 0]
    steps = [[]]
    out = merge_steps(xs, counts, steps)
    return [out, steps[0], counts[0], counts[1]]

def counting(xs):
    counts = [0] * 100
    for x in xs:
        counts[x] = counts[x] + 1
    seen = ""
    for v in range(0, 100):
        if counts[v] > 0:
            if seen != "":
                seen = seen + ", "
            seen = seen + str(v) + " x" + str(counts[v])
    out = []
    for v in range(0, 100):
        for k in range(1, counts[v]+1):
            out = out + [v]
    return [out, [["counts: " + seen, out, len(out)]], 0, len(out)]

def plural(n, word):
    if n == 1:
        return "1 " + word
    return str(n) + " " + word + "s"

def numbers(xs):
    out = ""
    for x in xs:
        if out != "":
            out = out + " "
        out = out + str(x)
    return "[" + out + "]"
```

## README

# P045 - Sorting visualizer

A list of up to 12 numbers from 0 to 99, sorted step by step by bubble sort,
insertion sort, merge sort or counting sort. Every pass, insertion or merge
is shown, with a bar marking the part already in place, and each sort ends
with the comparisons and moves it took; or all four run side by side on the
same list.

- `main.eml` - the menu, the list and its checks, and the steps on screen
- `sorts.eml` - the four sorts, each reporting its steps and its counts

How each part works:

- Bubble sort, as in the corpus case `bubble-sort`, compares neighbours and
  swaps them when they are out of order; after pass p the last p values are
  in place, and a pass without a swap stops it early - one pass for a list
  already sorted.
- Insertion sort, as in `insertion-sort`, slides each value left past the
  larger ones before it; the first values are always in order among
  themselves. Its shifts equal bubble sort's swaps: both are the number of
  pairs out of order - 15 in the sample, 36 for nine numbers reversed.
- Merge sort, as in `merge-sort`, sorts each half and merges them, taking
  the smaller front value each time (the left one on a tie, so equal values
  keep their order); every merge is shown.
- Counting sort, as in `counting-sort`, compares nothing: it counts each
  value from 0 to 99 and writes them out in order. That only works because
  the values are small whole numbers.
- A comparison and a move mean slightly different things in each sort: a
  swap, a shift, or a value written into a merged or counted list.

What is checked: 2 to 12 numbers, each a whole number from 0 to 99,
separated by spaces or commas; anything else leaves the list as it was. An
empty answer cancels.

Sessions: `sessions/basic.in` runs all four sorts on the sample (eight
numbers with a repeat) and compares them; then nine numbers in reverse
order, where bubble sort makes 36 comparisons and 36 swaps, and six already
in order, where bubble sort stops after one pass and insertion sort shifts
nothing. `sessions/bad-input.in` gives menu choices 0 and x, an empty list,
one number, a list with x in it, 100, thirteen numbers and -1, then two
equal numbers, which every sort leaves alone.

Built on the verified corpus cases `bubble-sort`, `insertion-sort`,
`merge-sort` and `counting-sort` (the four sorts on fixed lists).