Magnitude Sorting

Most systems expose comparison sorting interfaces, because they're simple, but also from traditions.
To understand a mechanism sorting data based on the boolean result of another code fragment is easy,
and such a mechanism is sensible when the greater system can do but one thing at a time, regardless.
However, I enjoy thinking about systems which aren't constrained so, and these interfaces exposed at
a high-level pose issues.  I've thought a decent amount about how ``non-von Neumann'' machines could
cope with them, to unsatisfying conclusions.  The only way I can see to support a general comparison
sorting in a ``non-von Neumann'' computer is to have a network of smaller ``von Neumann'' computers.

Digital automatic computers only truly support the bit.  Abstract data types can be added just above
this level, and enforced, but must be chosen carefully; integers, addresses, and signed integers are
the most common examples of supported types, usually in a way that turns them into muck.  Generally,
to avoid muck, tagging is first added to the hardware, which simply uses bits representing integers,
representing types, with the tagging bits restricted as the enforcement.  It's easy to envision this
basic mechanism, distributed throughout a network of simple and small ``non-von Neumann'' computers.

It seems inherent to me that small such machines must be limited necessarily across their abilities,
and the only reasonable abstract data type I can see them supporting for sorting is the integer of a
signed or not signed kind; the matter is that specialized interfaces for sorting data, or telling it
to sort itself, are easily envisioned, also likely, and likely to support only integers, placing all
other types at a disadvantage.  To extend that scope of what can be done in sorting eventually makes
them tiny ``von Neumann'' computers, and I believe this to somewhat kill the purpose in having them.

Magnitude sorting is a better interface, I believe, even before delving into the issue of algorithms
that can sort integers more effectively than a comparison sort can; I'm concerned here entirely with
specialized hardware, not necessarily algorithms.  My solution to this problem is to recommend high-
level languages to support, at the very least, interfaces for magnitude sorting, alongside those for
comparison sorting.  These interfaces would demand code to translate input types to integer outputs,
magnitudes, rather than code to tell whether one input type precedes another or not; given that such
code fragments for comparison can be malformed, thus behaving inconsistently, I'm reasonably certain
that translating all comparison sorting to magnitude sorting be impossible, in the general case, but
a great many instances could be converted easily.  The base of the idea is, rather than treating the
type as a sortable type through code, use code to map the type to an inherently sortable type.  This
can be as simple as but field extraction, if a record is to be sorted according to an integer field,
to as complex as record convolution, if several fields of such a record would need to be considered.

I imagine simple hardware that can perform limited convolutions of its primary state for the purpose
with such simple operations as masking, restriction to a contiguous field, reordering, but not those
such as indirection to some other machine, or perhaps memory.  It's clear how these basic operations
can accommodate many conversions of comparison functions to magnitude determination functions; those
most important fields can be reordered according to precedence, irrelevant such fields can be masked
away, and the restriction could be a more efficient form of masking where applicable.  More of these
local operations could be added after studying more common comparison sorting functions and whatnot.
If the values to be sorted were irrevocably changed then they could be tracked by giving each unit a
slot to hold an identifier for elements of the original unordered set, and this solves that problem.

Despite these paragraphs, it's generally better to avoid sorting where possible or, in a system with
say one server and many clients, to require all sorting of message fields to be done by the clients;
then, checking whether a sequence be sorted or not is trivial and requires no special optimizations.
.