Paper by Erik D. Demaine

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.

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).

The paper is 12 pages.

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 March 27, 2017 by Erik Demaine.