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.
|Number of pages||7|
|Journal||International Journal of Parallel and Distributed Systems and Networks|
|Publication status||Published - 1999|