# Stably sort N elements in this restricted "cmov" language

The following problem is taken from the real world — but indubitably code-golf! In this puzzle, the programming language is fixed, and your job is to write the most efficient program in this fixed language. The language has no loops; a program is a straight-line sequence of instructions. Each instruction consists of exactly three characters — an opcode and two operands — and in fact there are only four possible opcodes:

• <xy — Compare the value in register x to the value in register y; set flag = L if x < y; flag = G if x > y; and flag = Z otherwise.
• mxy — Set the value in register x equal to the value in register y. (This is "move.")
• lxy — If flag = L, then set the value in register x equal to the value in register y; otherwise do nothing. (This is "conditional move," or "cmov".)
• gxy — If flag = G, then set the value in register x equal to the value in register y; otherwise do nothing. (This is "conditional move," or "cmov".)

For example, the program mca <ba lcb means "Set register c equal to the minimum of a and b."

The program mty <zy lyz lzt means "Stably sort the values in registers y and z." That is, it sets y to the minimum of y and z (breaking ties in favor of y) and sets z to the maximum of y and z (breaking ties in favor of z).

The following 16-instruction program stably sorts the values in registers x, y, z:

<zy mtz lzy lyt
max mby mcz
<yx lay lbx
<zx lcx lbz
mxa myb mzc


Your task is to find the shortest program that stably sorts four registers w, x, y, z.

A trivial Python implementation is available here if you want to test your solution before (or after) posting it.

• You'll receive imaginary bonus points if you find a second (shortest) program that stably sorts five registers. Dec 19, 2023 at 3:00
• This reminds me of Zachlike programming, specifically the programming in Shenzhen I/O.
– Tbw
Dec 19, 2023 at 4:21
• What does "stable" sorting mean when values that compare as equal are actually equal? Dec 19, 2023 at 6:06
• I mean if "equal" truly means "equal" and not just "equivalent" then you cannot tell whether equal elements have been swapped or not. Dec 19, 2023 at 18:41
• My point is neither deep not philosophical. Your wording ("cmov", "register") strongly suggests an assembly-like setting.The average reader will understand a register as carrying a simple value, a number, not something that would have "attributes that do not participate in equality". Dec 20, 2023 at 3:04

# 21 instr

  '<wx', 'gtw', 'gwx', 'gxt',
'<xy', 'guy', 'gyx', 'gxu',
'<yz', 'gtz', 'gzy', 'gyt',
'<wx',        'gxw', 'gwu',
'<xy',        'gyx', 'gxt',
'<wx',        'gxw', 'gwt'


Try it online!

Neil suggests that reordering into this may get more clear:

<wx gtw gwx gxt
<xy gty gyx gxt
<wx     gxw gwt
<yz gtz gzy gyt
<xy     gyx gxt
<wx     gxw gwt


This looks more like insertion sort

For large enough amount of element, a $$\\tilde {\mathrm O} \left(n\right)\$$ sorting algorithm exist. Here I construct a $$\\mathrm O \left(n \log^2 n\right)\$$ one using a $$\\mathrm O \left(n \log n\right)\$$ sorting network, which seems reducible: (say the input is A[0..n-1]

1. Set O to min(A) and I to max(A).

Notice that if O = I, then all elements are equal, and no swap would apply.

1. Let B[i][j] = i & (1 << j) ? I : O for 0 <= j < log2(n).

2. Do sorting network on A, each element A[i] together with B[i].

To do a multi-element compare:

T = O
if (P[0] < Q[0]) T = I
if (P[1] > Q[1]) T = O
if (P[1] < Q[1]) T = I
if (P[2] > Q[2]) T = O
if (P[2] < Q[2]) T = I
...
if (P[9] > Q[9]) T = O
if (P[9] < Q[9]) T = I
if (T > O) swap


This makes a swap in $$\\mathrm O \left( \log n\right)\$$

• This also reduces the three-register sort from 16 to 12 instructions.
– Neil
Dec 19, 2023 at 8:21
• Very nice! But more boringly symmetric than I'd expected. ;) I mean, it's literally bubble sort — bubble max(w,x,y,z) up to z, then bubble max(w,x,y) up to y, etc. Do you think it's generally the case that stable-sorting n elements in this restricted language requires (n-1) + (n-2) + ... + 2 + 1 < instructions? Dec 19, 2023 at 16:40
• @Quuxplusone I can sort n elements in $\text O(n \log^3 n)$ by finding two different elements to record position, and it should be far from optimal
– l4m2
Dec 20, 2023 at 3:54
• @Quuxplusone Pseudo-code
– l4m2
Dec 20, 2023 at 15:28
• <wx gtw gwx gxt <xy gty gyx gxt <wx gxw gwt <yz gtz gzy gyt <xy gyx gxt <wx gxw gwt shows more clearly what's going on, and also uses one fewer temporary to boot. The three-register sort is also now only 11 instructions: <xy gty gyx gxt <yz gtz gzy gyt <xy gyx gxt.
– Neil
Dec 24, 2023 at 12:22

## 23 22 instructions

Here's a different approach from l4m2's bubble sort — we can use insertion sort. We start by sorting x, y, z. Then we insert w in its proper place by starting at the top and working downward: If w > z, insert it and bump out the old z into q. If w > y, insert q and bump out the old y into q. And so on. An "unoptimized" sequence of instructions that works for that second part is:

mpw mtx muy mvz
<vp mqp lqv lvp
mau <up luq lqa
<tp lpt ltq
mwp mxt myu mzv


I can optimize that and append it to l4m2's 12 Neil's 11-instruction sort3 to produce this 23 22-instruction sort4:

<zy lty lyz lzt
<yx ltx lxy lyt
<zy lyz lzt
mqw <zw lqz lzw
<yw lty lyq lqt
<xw lwx lxq


But I don't see how to shrink it further than that.

And it still uses 6 < instructions. Is it conceivably possible to use only 5? Here's a 20-instruction sort4 (based on this sorting network) that uses only 5 comparisons but is not stable, so it doesn't fulfill the challenge:

<wy gtw gwy gyt
<xz gtx gxz gzt
<wx gtw gwx gxt
<yz gty gyz gzt
<xy gtx gxy gyt


I'm also (finally) realizing that I should have given not only cmovl and cmovg but also cmovle and cmovge as primitives; I wonder if that would have helped at all.

• Since sort3 is now down to 11 instructions, this can be reduced to 22: <xy gty gyx gxt <yz gtz gzy gyt <xy gyx gxt mqw <zw lqz lzw <yw lty lyq lqt <xw lwx lxq.
– Neil
Dec 24, 2023 at 12:25
• Oh, you have a tweaked sort3... I'm sure you can figure out what I meant...
– Neil
Dec 24, 2023 at 12:27

## 32 instructions

Here's yet another approach: mergesort. This successfully minimizes the number of < operations to 5, but we pay for it with a lot more cmovs. We start by sorting the sublists {w, x} and {y, z}; then we merge those two lists. But "merge the two lists" is harder than it sounds. I wrote out the complete game tree; e.g. "First compare wy. If true, the next step will be to compare xy; otherwise, the next step will be to compare wz" and so on. Then rewrite as "If wy, set i,jx,y; otherwise, set i,jw,z. The next step is to compare ij" and so on. That gives an unoptimized program like this:

<wx gtw gwx gxt
<yz gty gyz gzt
maw mbx mcy mdz
<ac
mwa mib mjc m1c m2d m3c m4d m5b m6d m7d m8b
gwc gia gjd g1b g2d g3d g4b g5a g6b g7a g8b
<ij
mxi
gxj g15 g26 g37 g48
<bd
my1 mz2
gy3 gz4


My best-optimized version takes 32 instructions:

<wx gtw gwx gxt
<yz gty gyz gzt
m3y m4z m5x m6z m7z m8x
<wy g48 g5w g6x g7w gwy gx5 gy8 g3z
<x3 gx3 gy5 gz6 g37 g48
<8z gy3 gz4