## Sort Four

### April 11, 2017

Sorting is done like this. First, sort the first two items in the input. Second, sort the last two items in the input. Third, compare the two low items of the first two and the last two; the lower of those two items is the lowest in the final output. Fourth, compare the two high items of the first two and the last two; the higher of those two items is the highest in the final output. Fifth, compare the two remaining items, putting them in the correct order. That’s a mouthful to say, and even more complicated to code:

(define (sort4 a b c d) (let ((ab (if (< a b) (list a b) (list b a))) (cd (if (< c d) (list c d) (list d c)))) (let ((first #f) (mid1 #f) (mid2 #f) (last #f)) (cond ((< (car ab) (car cd)) (set! first (car ab)) (set! mid1 (car cd))) (else (set! first (car cd)) (set! mid1 (car ab)))) (cond ((< (cadr ab) (cadr cd)) (set! last (cadr cd)) (set! mid2 (cadr ab))) (else (set! last (cadr ab)) (set! mid2 (cadr cd)))) (if (< mid1 mid2) (list first mid1 mid2 last) (list first mid2 mid1 last)))))

Since there are only 4! = 24 possible inputs, it is easy to show that the program works in all cases:

> (for-each (lambda (xs) (display xs) (display " => ") (display (apply sort4 xs)) (newline)) (permutations '(1 2 3 4))) (4 3 2 1) => (1 2 3 4) (3 4 2 1) => (1 2 3 4) (2 4 3 1) => (1 2 3 4) (4 2 3 1) => (1 2 3 4) (3 2 4 1) => (1 2 3 4) (2 3 4 1) => (1 2 3 4) (1 4 3 2) => (1 2 3 4) (4 1 3 2) => (1 2 3 4) (3 1 4 2) => (1 2 3 4) (1 3 4 2) => (1 2 3 4) (4 3 1 2) => (1 2 3 4) (3 4 1 2) => (1 2 3 4) (2 1 4 3) => (1 2 3 4) (1 2 4 3) => (1 2 3 4) (4 2 1 3) => (1 2 3 4) (2 4 1 3) => (1 2 3 4) (1 4 2 3) => (1 2 3 4) (4 1 2 3) => (1 2 3 4) (3 2 1 4) => (1 2 3 4) (2 3 1 4) => (1 2 3 4) (1 3 2 4) => (1 2 3 4) (3 1 2 4) => (1 2 3 4) (2 1 3 4) => (1 2 3 4) (1 2 3 4) => (1 2 3 4)

You can run the program at http://ideone.com/3jmcKZ.

Pages: 1 2

Like this?

Two versions using Clojure:

Here’s a depth-3 Parallel Fouring Machine program, P, tested with an interpreter written in Python (see below). Parallel Fouring Machine programs are binary trees of commands that act on four registers so that each command sorts both the two indicated registers and the two complementary registers, in parallel, and they continue to the left branch if either pair was swapped, else to right.

Clearly this program P always executes the same three parallel comparisons, so it corresponds to six sequential comparisons. Is off by one close enough? (I was not able to generate even all depth-4 Sequential Fouring Machine programs, let alone enough of the required depth-5. It was a combinatorial explosion, and I had no ideas to prune the search space. So I went on to discover the Parallel Fouring Machine instead. For the Journal of Negative Results, maybe.)

Here’s the interpreter, F, in Python.

There are only 36 depth-3 Parallel Fouring Machine programs that always sort the four registers. Some might contain the clue to the 5-step sequential sorting problem, if they were investigated more closely.

For such a small number of items to sort, we will avoid memory writes, by expanding the decision tree, and keeping the four elements in registers until it’s time to store them in the resulting sorted vector. Between 4 and 5 tests are needed to reach the leaves of the decision tree (on average for equiprobable permutations: 4.5).

@Mike, I should have had the courage :) Here’s an interpreter for a simpler Fouring Machine whose six opcodes just sort a pair of registers without branching anywhere. A program is a sequence of opcodes.

It’s a combinatorial piece of cake to generate a 5-command solution now. There are 12. Here’s one, which turns out to be precisely your (Mike’s) solution.

One could write a compiler to get a Python (or Scheme (or C (or why not some assembler))) program.

This is Scheme.

This scheme version is nice, but scheme compilers won’t be able to avoid the fifth comparison, when it’s useless. You will get exactly 5 comparison, why the Common Lisp expanded version has 4.5 comparisons on average.

MUMP V1:

SORT4 ;New routine

1 (N1,N2,N3,N4) ;

N ARR,I

; When the numbers are placed into the array “ARR”, they are automatically placed in sorted order

F I=N1,N2,N3,N4 S ARR(I)=””

; Write the numbers starting at the least

S I=”” F S I=$O(ARR(I)) Q:I=”” W !,I

Q

MCL> D 1^SORT4(99,87,65,7)

7

65

87

99