NeatSort - A practical adaptive algorithm

Preprint English OPEN
La Rocca, Marcello ; Cantone, Domenico (2014)
  • Subject: C.2.2 | 68W01, 68W40 | Computer Science - Data Structures and Algorithms

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 $\Omega (|X|)$ lower bound and a $\mathcal{O}(|X|\log|X|)$ 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, \textit{NeatSort} has proven itself competitive with (and often better than) \textit{qsort} and any \textit{Random Quicksort} implementation, even on random arrays.
  • References (11)
    11 references, page 1 of 2

    [Estivill-Castro and Wood(1989)] Vladimir Estivill-Castro and Derick Wood. A new measure of presortedness. Information and Computation, 83(1):111{119, 1989.

    [Estivill-Castro and Wood(1990)] Vladimir Estivill-Castro and Derick Wood. A generic adaptive sorting algorithm. University of Waterloo, Computer Science Department, 1990.

    [Estivill-Castro and Wood(1992)] Vladmir Estivill-Castro and Derick Wood. A survey of adaptive sorting algorithms. ACM Computing Surveys (CSUR), 24(4):441{476, 1992.

    [Knuth(1973a)] Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming, section 5.2.1. Addison-Wesley, Reading, Massachusetts, second edition, 10 January 1973a. Full INBOOK entry (w series).

    [Knuth(1973b)] Donald E. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming, page 161. Addison-Wesley, Reading, Massachusetts, second edition, 10 January 1973b. Full INBOOK entry (w series).

    [Levcopoulos and Petersson(1989)] Christos Levcopoulos and Ola Petersson. A note on adaptive parallel sorting. Information processing letters, 33(4):187{191, 1989.

    [Levcopoulos and Petersson(1990)] Christos Levcopoulos and Ola Petersson. Sorting shu ed monotone sequences. Springer, 1990.

    [Mannila(1985)] Heikki Mannila. Measures of presortedness and optimal sorting algorithms. Computers, IEEE Transactions on, 100(4):318{325, 1985.

    [Mo at and Petersson(1991)] Alistair Mo at and Ola Petersson. Historical searching and sorting. In ISA'91 Algorithms, pages 263{272. Springer, 1991.

    [Petersson and Mo at(1995)] Ola Petersson and Alistair Mo at. A framework for adaptive sorting. Discrete Applied Mathematics, 59(2):153{179, 1995.

  • Metrics
    No metrics available
Share - Bookmark