The heap-mergesort

R. A. Chowdhury; S. K. Nath; M. Kaykobad

doi:10.1016/s0898-1221(00)00075-4

The heap-mergesort

R. A. Chowdhury
, S. K. Nath
, M. Kaykobad

Computer Science

Bangladesh University of Engineering and Technology

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

Abstract

In this paper, we present a new mergesort algorithm which can sort n(= 2^h+1 - 1) elements using no more than nlog₂(n + l)-(13/12)n-l element comparisons in the worst case. This algorithm includes the heap (fine heap) creation phase as a pre-processing step, and for each internal node v, its left and right subheaps are merged into a sorted list of the elements under that node. Experimental results show that this algorithm requires only n log₂(n +1) - 1.2n element comparisons in the average case. But it requires extra space for n LINK fields.

Original language	English
Pages (from-to)	193-197
Number of pages	5
Journal	Computers and Mathematics with Applications
Volume	39
Issue number	7-8
DOIs	https://doi.org/10.1016/s0898-1221(00)00075-4
State	Published - Mar 1 2000

Keywords

Complexity
Fine heap
Heap-mergesort
Mergesort

Access to Document

10.1016/s0898-1221(00)00075-4

Cite this

@article{bfe046f6622a4491b6d244b0be2b42ec,

title = "The heap-mergesort",

abstract = "In this paper, we present a new mergesort algorithm which can sort n(= 2h+1 - 1) elements using no more than nlog2(n + l)-(13/12)n-l element comparisons in the worst case. This algorithm includes the heap (fine heap) creation phase as a pre-processing step, and for each internal node v, its left and right subheaps are merged into a sorted list of the elements under that node. Experimental results show that this algorithm requires only n log2(n +1) - 1.2n element comparisons in the average case. But it requires extra space for n LINK fields.",

keywords = "Complexity, Fine heap, Heap-mergesort, Mergesort",

author = "Chowdhury, \{R. A.\} and Nath, \{S. K.\} and M. Kaykobad",

year = "2000",

month = mar,

day = "1",

doi = "10.1016/s0898-1221(00)00075-4",

language = "English",

volume = "39",

pages = "193--197",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

number = "7-8",

}

TY - JOUR

T1 - The heap-mergesort

AU - Chowdhury, R. A.

AU - Nath, S. K.

AU - Kaykobad, M.

PY - 2000/3/1

Y1 - 2000/3/1

N2 - In this paper, we present a new mergesort algorithm which can sort n(= 2h+1 - 1) elements using no more than nlog2(n + l)-(13/12)n-l element comparisons in the worst case. This algorithm includes the heap (fine heap) creation phase as a pre-processing step, and for each internal node v, its left and right subheaps are merged into a sorted list of the elements under that node. Experimental results show that this algorithm requires only n log2(n +1) - 1.2n element comparisons in the average case. But it requires extra space for n LINK fields.

AB - In this paper, we present a new mergesort algorithm which can sort n(= 2h+1 - 1) elements using no more than nlog2(n + l)-(13/12)n-l element comparisons in the worst case. This algorithm includes the heap (fine heap) creation phase as a pre-processing step, and for each internal node v, its left and right subheaps are merged into a sorted list of the elements under that node. Experimental results show that this algorithm requires only n log2(n +1) - 1.2n element comparisons in the average case. But it requires extra space for n LINK fields.

KW - Complexity

KW - Fine heap

KW - Heap-mergesort

KW - Mergesort

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

U2 - 10.1016/s0898-1221(00)00075-4

DO - 10.1016/s0898-1221(00)00075-4

M3 - Article

AN - SCOPUS:0034174164

SN - 0898-1221

VL - 39

SP - 193

EP - 197

JO - Computers and Mathematics with Applications

JF - Computers and Mathematics with Applications

IS - 7-8

ER -

The heap-mergesort

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this