Emerge-Sort

Emerge-Sort is about emergent sorting; how sorting can emerge out of agents that do simple (more or less) things locally, without knowing which way their sequence will be sorted into.

A draft of this work appeared some time ago:

Emerge-Sort: Converging to Ordered Sequences by Simple Local Operators

The high-level concept is described in the following publication:

            D. Kalles, V. Mperoukli and A. Papandreadis. “Emerge-Sort: Swarm Intelligence Sorting”, Panhellenic Conference on Artificial Intelligence, 2012.

This technique sorts in O(n2) and operates on triples of numbers (that's the locality of the operator). We expect that the larger the scope of the operator, the more we might be moving away from O(n2) towards O(n logn). Is this linked to a price of anarchy induced by myopic small neighbourhoods? That's what we are looking into currently and it's proving tricky to show theoretically that sequences will eventually get sorted in O(n2), which is what we observe.

Additionally, we are interested into looking which combinations of local operators are more effective and we are using genetic algorithms to do just that.

Here's Emerge-Sort on the web if you want to experiment online. Contact me if you want the software at a desktop or to install it at another server.

Here's a gradual introduction to Emerge-Sort:

    1) Read the conference paper.

    2) Go through the short presentation video (pdf, wmv) and, then, through the example video (pdf, wmv); to play the .wmv files, VLC is strongly recommended.

    3) Have a look at how to use the web application.

To start looking into massive sequences and to experiment with many more operators we are also looking into porting our software to the grid. If you are interested, do let me know. We've been busy on that, we have some code that works on the grid, but we are trying to make it smarter still.