Show simple item record

dc.contributor.authorKhalaila, Ahmad H.
dc.contributor.authorEliassen, Frank
dc.date.accessioned2006-11-28T07:45:28Z
dc.date.available2006-11-28T07:45:28Z
dc.date.issued1997-05
dc.description.abstractThis paper proposes an external sorting algorithm for large data as an alternative to the widely used merge-sort algorithm. The algorithm we present is an application of the widely known quick-sort algorithm to large sequences of data stored externally on a disk device. The problem with the merge-sort algorithm is not its time complexity but the large amount of time it requires to output its first results. This is a serious problem in the context of pipelined processing, since the operations consuming its result will have to wait all that time before they can start their processing, thus limiting the degree of vertical parallelism achievable by pipelined processing Using quick-sort instead of merge-sort for external sorting in pipelined data processing systems results in an optimization in the order of $log N$ (where N is the size of the data sequence to be sorted) for the entire query pipeline where the sorting operation is involved.en
dc.format.extent120871 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttps://hdl.handle.net/10037/370
dc.identifier.urnURN:NBN:no-uit_munin_243
dc.language.isoengen
dc.publisherUniversitetet i Tromsøen
dc.publisherUniversity of Tromsøen
dc.relation.ispartofseriesTekniske rapporter / Institutt for informatikk 30(1997)en
dc.rights.accessRightsopenAccess
dc.subjectVDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420en
dc.subjectVDP::Teknologi: 500::Informasjons- og kommunikasjonsteknologi: 550en
dc.titleQuick- instead of Merge-sort for pipelines systemsen
dc.typeResearch reporten
dc.typeForskningsrapporten


File(s) in this item

Thumbnail
Thumbnail

This item appears in the following collection(s)

Show simple item record