Emerge-Sort: Converging to Ordered Sequences by Simple Local Operators
| dc.creator | Kalles, Dimitris | |
| dc.creator | Kaporis, Alexis | |
| dc.date | 2008-12-05 | |
| dc.date | 2009-03-10 | |
| dc.date.accessioned | 2026-07-07T12:50:11Z | |
| dc.date.available | 2026-07-07T12:50:11Z | |
| dc.description | In this paper we examine sorting on the assumption that we do not know in advance which way to sort a sequence of numbers and we set at work simple local comparison and swap operators whose repeating application ends up in sorted sequences. These are the basic elements of Emerge-Sort, our approach to self-organizing sorting, which we then validate experimentally across a range of samples. Observing an O(n2) run-time behaviour, we note that the n/logn delay coefficient that differentiates Emerge-Sort from the classical comparison based algorithms is an instantiation of the price of anarchy we pay for not imposing a sorting order and for letting that order emerge through the local interactions. | |
| dc.description | Contains 16 pages, 17 figures, 1 table. Text updated as of March 10, 2009. Submitted to a journal | |
| dc.identifier | https://arxiv.org/abs/0812.1126 | |
| dc.identifier | http://arxiv.org/abs/0812.1126 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/222610 | |
| dc.subject | Artificial Intelligence | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Emerge-Sort: Converging to Ordered Sequences by Simple Local Operators | |
| dc.type | text |