Improving performance of sorting small arrays on MIPS CPUs using bitonic sort and SIMD instructions

Even though sorting has been widely examined problem in computer science, its parallelization is still subject to many challenges, and draws much interest, even in recent years. This paper presents and examines a possible implementation of parallelized sorting for MIPS CPUs that relies on bitonic sorting networks and SIMD instructions. The main goal of the implementation was to create a set of fast algorithms for sorting arrays of small size (4, 8 and 16) that could be, in turn, applied within a larger, more general, sorting system. Developed algorithms are compared to corresponding cases of stl::sort algorithm in terms of execution time. Measured performance gains were significant.