  The emerging field of Diverse Intelligence seeks to identify, formalize, and
understand commonalities in behavioral competencies across a wide range of
implementations. Especially interesting are simple systems that provide
unexpected examples of memory, decision-making, or problem-solving in
substrates that at first glance do not appear to be complex enough to implement
such capabilities. We seek to develop tools to help understand the minimal
requirements for such capabilities, and to learn to recognize and predict basal
forms of intelligence in unconventional substrates. Here, we apply novel
analyses to the behavior of classical sorting algorithms, short pieces of code
which have been studied for many decades. To study these sorting algorithms as
a model of biological morphogenesis and its competencies, we break two
formerly-ubiquitous assumptions: top-down control (instead, showing how each
element within a array of numbers can exert minimal agency and implement
sorting policies from the bottom up), and fully reliable hardware (instead,
allowing some of the elements to be "damaged" and fail to execute the
algorithm). We quantitatively characterize sorting activity as the traversal of
a problem space, showing that arrays of autonomous elements sort themselves
more reliably and robustly than traditional implementations in the presence of
errors. Moreover, we find the ability to temporarily reduce progress in order
to navigate around a defect, and unexpected clustering behavior among the
elements in chimeric arrays whose elements follow one of two different
algorithms. The discovery of emergent problem-solving capacities in simple,
familiar algorithms contributes a new perspective to the field of Diverse
Intelligence, showing how basal forms of intelligence can emerge in simple
systems without being explicitly encoded in their underlying mechanics.
