Paper by Erik D. Demaine

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.

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

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated March 9, 2018 by Erik Demaine.