Distributed data structures for multikey sorting

A. Fellah, M. Abaza, A. Maamir

Research output: Contribution to journalJournal Articlepeer-review

2 Citations (Scopus)


Although a tremendous amount of research has been invested in developing sorting algorithms, multikey sorting has received little attention. In this paper, we introduce three data structures MKM, T-MKM, and R-MKM for multikey sorting. Moreover, we study the time and space complexities of these structures and compare them to that of MKT. We show that if T-MKM is evenly distributed over p nodes of a distributed system, then searching and sorting on τ keys K1, K2, ..., Kτ of d1, d2, ..., dτ distinct values take O(log[db/p]) and O(log([db/p]) × Πi=1,i≠b τ di), respectively where p is the number of processors, db is the size of the base key Kb, and n is the number of records to be sorted (db ≥ √n). In addition, we propose R-MKM structures to improve MKM in term of memory space. The time complexity to build such reduced structures in a distributed system is O(√nlog √n). Furthermore, these data structures would allow multikey sorting in any order in just one pass as opposed to previous work [1, 2] where sorting required several passes.

Original languageEnglish
Pages (from-to)62-68
Number of pages7
JournalInternational Journal of Parallel and Distributed Systems and Networks
Issue number2
Publication statusPublished - 1999


Dive into the research topics of 'Distributed data structures for multikey sorting'. Together they form a unique fingerprint.

Cite this