This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Similar articles in ISI Web of Science Alert me to new issues of the journal Add to Saved Citations Download to citation manager Request Permissions Request Reprints Add to My Marked Citations Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Al-Darwish, N. Search for Related Content Social Bookmarking                   What's this?

Formulation and analysis of in-place MSD radix sort algorithms

ICS Department, King Fahd University of Petroleum and Minerals, Dhahran, Saudi Arabia

We present a unified treatment of a number of related inplace MSD radix sort algorithms with varying radices, collectively referred to here as 'Matesort' algorithms. These algorithms use the idea of in-place partitioning which is a considerable improvement over the traditional linked list implementation of radix sort that uses O(n) space. The binary Matesort algorithm is a recast of the classical radixexchange sort, emphasizing the role of in-place partitioning and efficient implementation of bit processing operations. This algorithm is O(k) space and has O(kn) worst-case order of running time, where k is the number of bits needed to encode an element value and n is the number of elements to be sorted. The binary Matesort algorithm is evolved into a number of other algorithms including 'continuous Matesort' for handling floating point numbers, and a number of 'general radix Matesort' algorithms. We present formulation and analysis for three different approaches (sequential, divide-and-conquer and permutation-loop) for partitioning by the general radix Matesort algorithm. The divide-andconquer approach leads to an elegantly coded algorithm with better performance than the permutation-loop-based American Flag Sort algorithm.

Key Words: sorting algorithms • radix sort • MSD radix sort • Matesort • general radix Matesort • Quicksort

CiteULike    Connotea    Del.icio.us    Digg    Reddit    Technorati    What's this?