Hi,

I’ve been investigating sorting algorithms and I’m going to be hitting the GPU memory limit, so I’d very much like to use an in-place algorithm if possible, but I’m concerned I’ll take a big hit in speed over using an out-of-place radix sort for example.

I’m primarily concerned about sorting (int, int) key-value pairs, and the data I will be sorting will already be reasonably ordered.

It seems the best in-place sorting currently uses the bitonic sort:

http://www.informatik.uni-kiel.de/fileadmin/arbeitsgruppen/comsys/files/public/ppam09.pdf

Are there any other sorting algorithms (or combinations of algorithms) that I should consider that has lower complexity than the bitonic sort, but also lower memory usage than the radix sort?

Thanks,

Dan