Distributed data structures for multikey sorting

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 K¹, K², ..., K^τ of d¹, d², ..., d^τ distinct values take O(log[d^b/p]) and O(log([d^b/p]) × Π_i=1,i≠b ^τ dⁱ), respectively where p is the number of processors, d^b is the size of the base key K^b, and n is the number of records to be sorted (d^b ≥ √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.