Sorting using heap structure

Authors
Chowdhury, RA Kaykobad, M
Citation
Ra. Chowdhury et M. Kaykobad, Sorting using heap structure, INT J COM M, 77(3), 2001, pp. 347-354
Citations number
15
Categorie Soggetti
Engineering Mathematics
Journal title
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS
ISSN journal
00207160 → ACNP
Volume
77
Issue
3
Year of publication
2001
Pages
347 - 354
Database
ISI
SICI code
Abstract
In this paper we present a new sorting algorithm for heaps which can sort n ( = 2(h + 1) - 1) elements using no more than nlog(2)(n + 1) - (13/12)n - 1 element comparisons in the worst case (including the heap creation phase) . Experimental results show that this algorithm requires only nlog(2)(n + 1 ) - 1.2n element comparisons in the average case. However it requires extra space for n LINK fields.