Parallel integer sorting

Abstract

This paper presents algorithms and experiments for internal (in core) and external (secondary memory) parallel sorting. It concentrates on algorithms appropriate for medium scale MIMD parallel computers, with all experiments being performed on a 128 processor Fujitsu AP1000. Data sizes ranging from a few hundred thousand to a few hundred million elements are considered, with all elements being either 64 bit or 128 bit integers. The internal sorting algorithm is based on earlier work by Andrew Tridgell and Richard Brent[11], while the external sorting algorithm was developed for this paper. The paper also takes a quick look at serial sorting algorithms, as they play an important part as subroutines in the parallel sorting algorithms. Show more