Sorting sixteen numbers

摘要

Sorting is a basic operation in data processing. A common direction in research is to design fast methods that sort millions of numbers. The focus of this article is to sort 16 numbers. Let a hextuple be an unordered tuple of 16 numbers. Although the data may consist of thousands to millions of hextuples, the task is to sort the numbers in each hextuple. GPUs have become powerful coprocessors to CPUs. Sorting networks, originally meant for hardware implementation, are suitable for sorting many hextuples on GPUs. Batcher's sorting network for 16 numbers has ten parallel steps, whereas Van Voorhis's network has nine. Software implementations of the former are well-known and publicly available, whereas the latter seems to remain on paper. The main results in this article are implementations of Van Voorhis's network. After several iterations of improvement, the final implementation of Van Voorhis's network is more than ten percent faster than the existing code for Batcher's network. Insights gained in implementing Van Voorhis's network lead to an improved implementation of Batcher's network. The last result is useful for sorting more than 16 numbers.