Here is John McCarthy’s version of von Neumann’s multi-merge sort and this is the concise form. A too simple sort.

Sorting with Parity

We sometimes need to sort and report whether the resulting permutation of the members is odd. These programs reject lists with repeated elements. The sort routine here does this for an unsorted list of integers. Here is a more concise form. This version does it with one less sort and and also returns the sorted list along with an indication of sort parity. The question is posed as pe [2; 5; 4; 7; 1];; and answered as (true, [1; 2; 4; 5; 7]). The “true” indicates that it took an odd permutation to put the integers in order. This version and this boil down the code to export fewer names into the surrounding scope. Finally this version dispenses with unnecessary parentheses. Perhaps some will find it easier to read. I have not learned enough precedence rules to read it but the compiler does not complain and produces code that produces the same answers.

Some program Logic

Here we describe in prose some of the computed values.

Routine pe takes values such as [5; 3; 4; 7; 2], a list of integers, and returns a pair (false, [2; 3; 4; 5; 7]) which is a boolean and the sorted version of the input. The boolean indicates whether the permutation to sort the integers was odd.

numr produces a version of the list to be sorted where each number is paired with its ordinal in the original input. Its like adding line numbers to a program.

The sort identifier refers to this sort routine which takes a binary predicate, unlike the routine List.sort. Here the sort takes a function as argument that compares the original values.

mpa takes the sorted list of pairs, raises Repeated_Vertex upon repeated inputs, extracts the now sorted original input integers and forms a list of pairs (rb, ordinal) where rb is a mutable bool and the ordinal of one of the input integers.

These two lists are then named svl, the sorted list of input integers, and spl, the list of pairs. Array ar is formed with these pairs as elements. The ordinal portion of such a pair forms an index into this array. Following this chain thru the array follows cycles of the permutation.

Routine dp operates on each element of the array that has not yet been visited, as determined by the mutable bool. Each cycle of the permutation is traversed by the routine lop marking the elements of the cycle as visited. The parity of the number of array elements previously visited when we come to them as we pass down the array, is the parity of the permutation. This is a linear algorithm for determining the parity of a permutation.