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.

BibTeX

@Article{FunSort_DAM,
  AUTHOR        = {Therese Biedl and Timothy Chan and Erik D. Demaine and
                   Rudolf Fleischer and Mordecai Golin and James A. King and
                   J. Ian Munro},
  TITLE         = {{Fun}-{Sort}---or the Chaos of Unordered Binary Search},
  JOURNAL       = {Discrete Applied Mathematics},
  JOURNALURL    = {http://www.elsevier.com/locate/dam},
  VOLUME        = 144,
  NUMBER        = 3,
  MONTH         = {December},
  YEAR          = 2004,
  PAGES         = {231--236},

  doi           = {https://dx.doi.org/10.1016/J.DAM.2004.01.003},
  dblp          = {https://dblp.org/rec/journals/dam/BiedlCDFGKM04},
  comments      = {This paper is also available from
                   <A HREF="http://dx.doi.org/10.1016/j.dam.2004.01.003">ScienceDirect</A>.},
  length        = {10 pages},
  papers        = {FUN2001; FunSort_TR2001},
  replaces      = {FUN2001},
}

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)