**Reference**:- 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. **Abstract**:-
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 Θ(*n*^{2}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 Θ(*n*^{2}log*n*) by always picking two random cells and swapping their contents if they are not ordered correctly. **Comments**:- This paper is also available from ScienceDirect.
**Length**:- The paper is 10 pages.
**Availability**:- 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.

Last updated August 16, 2018 by Erik Demaine.