Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/21915

Fun-Sort - or the chaos of unordered binary search

Authors Biedl, T.
Chan, T.
Demaine, ED
Fleischer, R. HKUST affiliated (currently or previously)
Golin, M. View this author's profile
King, JA
Munro, JI
Issue Date 2004
Source Discrete applied mathematics , v. 144, (3), 2004, DEC 15, p. 231-236
Summary 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 Theta(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 Theta(n(2) log n) by always picking two random cells and swapping their contents if they are not ordered correctly. (C) 2004 Elsevier B.V. All rights reserved.
Subjects
ISSN 0166-218X
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST