Please use this identifier to cite or link to this item: doi:10.22028/D291-26093
Title: Smoothsort's behavior on presorted sequences
Author(s): Hertel, Stefan
Language: English
Year of Publication: 1982
OPUS Source: Saarbrücken, 1982
DDC notations: 004 Computer science, internet
Publikation type: Report
Abstract: In [5], Mehlhorn presented an algorithm for sorting nearly sorted sequences of length n in time 0(n(1+log(F/n))) where F is the number of initial inversions. More recently, Dijkstra[3] presented a new algorithm for sorting in situ. Without giving much evidence of it, he claims that his algorithm works well on nearly sorted sequences. In this note we show that smoothsort compares unfavorably to Mehlhorn's algorithm. We present a sequence of length n with O(nlogn) inversions which forces smoothsort to use time Omega(nlog n), contrasting to the time O(nloglogn) Mehlhorn's algorithm would need.
Link to this record: urn:nbn:de:bsz:291-scidok-40623
Series name: Bericht / A / Fachbereich Angewandte Mathematik und Informatik, Universität des Saarlandes
Series volume: 1982/11
Date of registration: 1-Aug-2011
Faculty: MI - Fakultät für Mathematik und Informatik
Department: MI - Informatik
Collections:SciDok - Der Wissenschaftsserver der Universität des Saarlandes

Files for this record:
File Description SizeFormat 
fb14_1982_11.pdf2,28 MBAdobe PDFView/Open

Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.