Paper by Erik D. Demaine

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