Fun-Sort-or the chaos of unordered binary search

Therese Biedl, Timothy Chan, Erik D. Demaine, Rudolf Fleischer, Mordecai Golin, James A. King, J. Ian Munro

Research output: Contribution to journalArticlepeer-review

Abstract

Usually, 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 θ(n2log 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 θ(n2log n) by always picking two random cells and swapping their contents if they are not ordered correctly.

Original languageEnglish (US)
Pages (from-to)231-236
Number of pages6
JournalDiscrete Applied Mathematics
Volume144
Issue number3
DOIs
StatePublished - Dec 15 2004
Externally publishedYes

Keywords

  • Binary search
  • Insertion-sort
  • Oblivious sorting

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Fun-Sort-or the chaos of unordered binary search'. Together they form a unique fingerprint.

Cite this