Paper by Erik D. Demaine

Reference:

Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, and J. Ian Munro, “Fun-Sort”, in Proceedings of the 2nd International Conference on Fun with Algorithms (FUN 2001), Isola d'Elba, Italy, May 29–31, 2001, pages 15–26.

BibTeX

@InProceedings{FUN2001,
  AUTHOR        = {Therese Biedl and Timothy Chan and Erik D. Demaine and
                   Rudolf Fleischer and Mordecai Golin and J. Ian Munro},
  TITLE         = {Fun-Sort},
  BOOKTITLE     = {Proceedings of the 2nd International Conference on Fun with
                   Algorithms (FUN 2001)},
  BOOKURL       = {http://www.di.unipi.it/fun01/},
  xEDITOR       = {Elena Lodi and Linda Pagli and Nicola Santoro},
  ADDRESS       = {Isola d'Elba, Italy},
  MONTH         = {May 29--31},
  YEAR          = 2001,
  PAGES         = {15--26},

  LENGTH        = {12 pages},
  PAPERS        = {FunSort_DAM; FunSort_TR2001},
}

Abstract:

In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements in n − 1 cycles, or time O(n³). Not-So-Dumb-Sort, which only tests adjacent cells, also sorts in n − 1 cycles, or in time O(n²). Guess-Sort, a randomized version of Dumb-Sort, runs in expected time O(n² log n). And Fun-Sort, an in-place variant of Insertion-Sort that performs repeated insertions by binary search into an initially unsorted array, sorts in time O(n² log n).

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (215k) and gzipped PostScript (107k).

See information on file formats.

[Google Scholar search]

Related papers:

FunSort_DAM (Fun-Sort—or the Chaos of Unordered Binary Search)

FunSort_TR2001 (Fun-Sort)