Sorting using heap structure

Rezaul Alam Chowdhury; M. Kaykobad

Sorting using heap structure

Rezaul Alam Chowdhury
, M. Kaykobad

Computer Science

Bangladesh University of Engineering and Technology

Research output: Contribution to journal › Article › peer-review

3 Scopus citations

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₂(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₂(n+1) - 1.2n element comparisons in the average case. However it requires extra space for n LINK fields.

Original language	English
Pages (from-to)	347-354
Number of pages	8
Journal	International Journal of Computer Mathematics
Volume	77
Issue number	3
State	Published - 2001

Keywords

Complexity
Fine heap
Heapsort
MDR-HEAPSORT
Mergesort

Cite this

@article{9f7968142fee4d1e8e7f20488279974a,

title = "Sorting using heap structure",

abstract = "In this paper we present a new sorting algorithm for heaps which can sort n (=2h+1-1) elements using no more than nlog2(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 nlog2(n+1) - 1.2n element comparisons in the average case. However it requires extra space for n LINK fields.",

keywords = "Complexity, Fine heap, Heapsort, MDR-HEAPSORT, Mergesort",

author = "Chowdhury, \{Rezaul Alam\} and M. Kaykobad",

year = "2001",

language = "English",

volume = "77",

pages = "347--354",

journal = "International Journal of Computer Mathematics",

issn = "0020-7160",

number = "3",

}

TY - JOUR

T1 - Sorting using heap structure

AU - Chowdhury, Rezaul Alam

AU - Kaykobad, M.

PY - 2001

Y1 - 2001

N2 - In this paper we present a new sorting algorithm for heaps which can sort n (=2h+1-1) elements using no more than nlog2(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 nlog2(n+1) - 1.2n element comparisons in the average case. However it requires extra space for n LINK fields.

AB - In this paper we present a new sorting algorithm for heaps which can sort n (=2h+1-1) elements using no more than nlog2(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 nlog2(n+1) - 1.2n element comparisons in the average case. However it requires extra space for n LINK fields.

KW - Complexity

KW - Fine heap

KW - Heapsort

KW - MDR-HEAPSORT

KW - Mergesort

UR - https://www.scopus.com/pages/publications/26444512198

M3 - Article

AN - SCOPUS:26444512198

SN - 0020-7160

VL - 77

SP - 347

EP - 354

JO - International Journal of Computer Mathematics

JF - International Journal of Computer Mathematics

IS - 3

ER -

Sorting using heap structure

Abstract

Keywords

Other files and links

Fingerprint

Cite this