NeatSort - A practical adaptive algorithm

We present a new adaptive sorting algorithm which is optimal for most disorder metrics and, more important, has a simple and quick implementation. On input $X$, our algorithm has a theoretical $\mathrm{\Omega }(\mathrm{\mid }X\mathrm{\mid })$ lower bound and a $\mathcal{O}(\mathrm{\mid }X\mathrm{\mid }\log \mathrm{\mid }X\mathrm{\mid })$ upper bound, exhibiting amazing adaptive properties which makes it run closer to its lower bound as disorder (computed on different metrics) diminishes. From a practical point of view, $\mathit{\text{NeatSort}}$ has proven itself competitive with (and often better than) $\mathit{\text{qsort}}$ and any $\mathit{\text{Random}}\mathit{\text{Quicksort}}$ implementation, even on random arrays.