# sorting on the GPU

**URL:** <https://forums.developer.nvidia.com/t/sorting-on-the-gpu/720>\
**Category:** CUDA Programming and Performance\
**Created:** [May 15, 2007, 1:39pm UTC](https://forums.developer.nvidia.com/t/sorting-on-the-gpu/720 "2007-05-15T13:39:21Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![alex.be](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@alex.be](https://forums.developer.nvidia.com/u/alex.be)\
**Post date:** [May 15, 2007, 1:39pm UTC](https://forums.developer.nvidia.com/t/sorting-on-the-gpu/720/1 "2007-05-15T13:39:21Z")

</div>

I was curious about what algorithms people use here to sort data on the GPU. The bitonic sort example NVIDIA proposes in the template projects only works for n elems = n threads and as such has some serious limitations (max 512 elems to sort, and then only 16 registeres available per thread).

Has anybody tackled the problem yet? I have a big array of 1024-2048 elems I want to sort optimally (some variations of bin sort-bubble sort-selection sort I tried we’re far from satisfactory with performance /6 or /10 compared to bitonic)

I read about the adaptive bitonic sort but cannot find some meta code or implementation?

---

<div class="post-metadata">

**Author:** ![Simon\_Green](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Simon\_Green](https://forums.developer.nvidia.com/u/Simon_Green)\
**Post date:** [May 15, 2007, 2:09pm UTC](https://forums.developer.nvidia.com/t/sorting-on-the-gpu/720/2 "2007-05-15T14:09:12Z")

</div>

To sort larger arrays you would have each block sort a subset of the array in shared memory, and then merge the sorted sub-arrays. Unfortunately doing a merge efficiently in parallel is not easy.

Here’s a reference on adaptive bitonic sort:  
[url=“[Institute of Computer Science II](http://cg.cs.uni-bonn.de/docs/publications/2006/gress-2006-gpu-abisort.pdf)”][Institute of Computer Science II](http://cg.cs.uni-bonn.de/docs/publications...gpu-abisort.pdf%5B/url%5D)

GPUsort uses a similar algorithm and you can download their implementation here:  
[url=“[GPUSORT](http://gamma.cs.unc.edu/GPUSORT/index.html)”][http://gamma.cs.unc.edu/GPUSORT/index.html[/url]](http://gamma.cs.unc.edu/GPUSORT/index.html%5B/url%5D)

We have an efficient CUDA implementation of radix sort which should be in a future release of the SDK.

---

<div class="post-metadata">

**Author:** ![Mu-Chi\_Sung](https://developer.download.nvidia.com/images/forums/profile-default-devtalk-84.png) [@Mu-Chi\_Sung](https://forums.developer.nvidia.com/u/Mu-Chi_Sung)\
**Post date:** [May 20, 2007, 1:02pm UTC](https://forums.developer.nvidia.com/t/sorting-on-the-gpu/720/3 "2007-05-20T13:02:48Z")

</div>

> [@](#):
>
> To sort larger arrays you would have each block sort a subset of the array in shared memory, and then merge the sorted sub-arrays. Unfortunately doing a merge efficiently in parallel is not easy.
> 
> Here’s a reference on adaptive bitonic sort:
> 
> http://cg.cs.uni-bonn.de/docs/publications…gpu-abisort.pdf
> 
> GPUsort uses a similar algorithm and you can download their implementation here:
> 
> http://gamma.cs.unc.edu/GPUSORT/index.html
> 
> We have an efficient CUDA implementation of radix sort which should be in a future release of the SDK.
> 
> [snapback]197190[/snapback]

I did implement a “load-balanced” radix sort using CUDA. However it’s pretty slow since I am new to CUDA. But can u suggest what kind of radix sort will be used in the next release? Just want to make sure I am digging into the right way. Thanks!