Project 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.
2 modules · 2 recorded sessionstext-menu UI in the terminalupdated 2026-10-10
Every screen below was recorded under CPython. When this page was built, the EML interpreter replayed each session from the same input and printed the same bytes.
About
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 screensorts.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).
Recorded sessions
What the screen shows while someone uses the program. Each typed line appears after its prompt, the way a terminal shows it.
bad-input
interpreter: byte-equal== 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.
What was typed (22 lines)
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
basic
interpreter: byte-equal== 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.
What was typed (14 lines)
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
Modules
The program as written, entry module first. Each module transpiles to its own Python file, which is what eml project run executes.
main.eml(entry)
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 (main.py)
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 (sorts.py)
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 + "]"