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

Fun-sort

Authors Biedl, Therese
Chan, Timothy
Demaine, Erik D.
Fleischer, Rudolf H.
Golin, Mordecai J.
Munro, J. Ian
Issue Date 2001-02-20
Summary In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements in n-1 cycles, or time O(n3). Not-So-Dumb-Sort, which only tests adjacent cells, also sorts in n-1 cycles, or in time O(n2). Guess-Sort, a randomized version of Dumb-Sort, runs in expected time O(n2 log n). And Fun-Sort, an in-place variant of Insertion-Sort that performs repeated insertions by binary search into an initially unsorted array, sorts in time O(n2 log n).
Subjects
Language English
Format Technical report
Access
Files in this item:
File Description Size Format
200103.pdf 243341 B Adobe PDF