Affiliations: Computer Information Systems Department, Jordan University of Science and Technology, P.O. Box 3030, Irbid 22111, Jordan, e‐mail: [email protected] | Computer Science Department, New York Institute of Technology, P.O. Box 940650, Amman 11194, Jordan, e‐mail: [email protected]
Abstract: This paper presents a new in‐place pseudo linear radix sorting algorithm. The proposed algorithm, called MSL (Map Shuffle Loop) is an improvement over ARL (Maus, 2002). The ARL algorithm uses an in‐place permutation loop of linear complexity in terms of input size. MSL uses a faster permutation loop searching for the next element to permute group by group, instead of element by element. The algorithm and its runtime behavior are discussed in detail. The performance of MSL is compared with quicksort and the fastest variant of radix sorting algorithms, which is the Least Significant Digit (LSD) radix sorting algorithm (Sedgewick, 2003).
