Publication

Smoothsort revisited

Bron, C. & Hesselink, W. H., 13-Sep-1991, In : Information Processing Letters. 39, 5, p. 269-276 8 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard

Documents

  • 1991InfProcLettBron.pdf

    Final publisher's version, 744 KB, PDF document

A renewed analysis of Dijkstra's array sorting algorithm Smoothsort showed that the removal of a complexity improved the performance. The resulting algorithm has a worst-case behaviour of order N.log N. In the average case, it has more or less the same speed as heapsort. For arrays that are initially almost sorted, it is much faster than heapsort and can compete with quicksort. The correctness is argued by means of invariants. The performance is measured in terms of comparisons and exchanges, both in the analysis of worst-case behaviour and in the experimental data.

Original languageEnglish
Pages (from-to)269-276
Number of pages8
JournalInformation Processing Letters
Volume39
Issue number5
Publication statusPublished - 13-Sep-1991

    Keywords

  • ANALYSIS OF ALGORITHMS, DESIGN OF ALGORITHMS, PERFORMANCE EVALUATION, SORTING

ID: 6298822