## Abstract

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^{1}, K^{2}, ..., K^{τ} of d^{1}, d^{2}, ..., d^{τ} distinct values take O(log[d^{b}/p]) and O(log([d^{b}/p]) × Π_{i=1,i≠b} ^{τ} d^{i}), 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.

Original language | English |
---|---|

Pages (from-to) | 62-68 |

Number of pages | 7 |

Journal | International Journal of Parallel and Distributed Systems and Networks |

Volume | 2 |

Issue number | 2 |

Publication status | Published - 1999 |