Paper by Erik D. Demaine

Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, and J. Ian Munro, “Fun-Sort—or the Chaos of Unordered Binary Search”, Discrete Applied Mathematics, volume 144, number 3, December 2004, pages 231–236.

Usally, binary search only makes sense in sorted arrays. We show that insertion sort based on repeated “binary searches” in an initially unsorted array also sorts n elements in time Θ(n2 log n). If n is a power of two then the expected termination point of a binary search in a random permutation of n elements is exactly the cell where the element should be if the array was sorted. We further show that we can sort in expected time Θ(n2 log n) by always picking two random cells and swapping their contents if they are not ordered correctly.

This paper is also available from ScienceDirect.

The paper is 10 pages.

The paper is available in PostScript (309k), gzipped PostScript (146k), and PDF (130k).
See information on file formats.
[Google Scholar search]

Related papers:
FUN2001 (Fun-Sort)
FunSort_TR2001 (Fun-Sort)

See also other papers by Erik Demaine.
These pages are generated automagically from a BibTeX file.
Last updated June 13, 2024 by Erik Demaine.