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
Last updated August 16, 2018 by