Paper by Erik D. Demaine

Reference:
Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, and J. Ian Munro, “Fun-Sort”, Technical Report HKUST-TCSC-2001-03, Hong Kong University of Science and Technology, February 2001.
BibTeX
@TechReport{FunSort_TR2001,
  AUTHOR        = {Therese Biedl and Timothy Chan and Erik D. Demaine and
                   Rudolf Fleischer and Mordecai Golin and J. Ian Munro},
  TITLE         = {Fun-Sort},
  NUMBER        = {HKUST-TCSC-2001-03},
  NUMBERURL     = {http://www.cs.ust.hk/tcsc/RR/2001-03.ps.gz},
  INSTITUTION   = {Hong Kong University of Science and Technology},
  MONTH         = {February},
  YEAR          = 2001,

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

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(n3). Not-So-Dumb-Sort, which only tests adjacent cells, also sorts in n − 1 cycles, or in time O(n2). Guess-Sort, a randomized version of Dumb-Sort, runs in expected time O(n2 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(n2 log n).

Length:
The paper is 12 pages.

Availability:
The paper is available in PostScript (189k) and gzipped PostScript (75k).
See information on file formats.
[Google Scholar search]

Related papers:
FunSort_DAM (Fun-Sort—or the Chaos of Unordered Binary Search)
FUN2001 (Fun-Sort)


See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated January 22, 2026 by Erik Demaine.