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, exhib... View more
  • 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
Share - Bookmark