Jordan University of Science and Technology

Hierarchical Radix Sorting

Authors:  F. El-Aker and A. Al-Badarneh

This paper presents an in-place pseudo linear radix sorting algorithm, called Multi-Pivot Radix Exchange (MPRE). MPRE is an implementation of radix exchange, dividing into many partitions instead of two partitions. Radix exchange is also known as Binary Quick Sort (BQS). MPRE is also used as a pre-processing step to an efficient radix sorting algorithm, called Hierarchical MPRE in which a re-implemented radix exchange (Re-BQS) is executed after the pre-processing step, which executes MPRE. Hierarchical MPRE is more efficient than the radix sorting LSD, algorithm, when sorting 63 bit integers. LSD radix sorting is not in-place. In the results section, we also implement Hierarchical MSL, applying MSL [1] as a pre-processing step, with similar results.