Sorting on GPU

Posted Mar 7, 2025 14:15 UTC (Fri) by jezuch (subscriber, #52988)
Parent article: Two new graph-based functional programming languages

> 68 seconds on a single thread, 25 seconds on four threads (although this may have been impacted by hyperthreading on the virtual machine, which had access to four dedicated vCPUs), and 0.78 seconds on the GPU.

Nice. I wasn't keeping up with developments in sorting algorithms so I completely missed how you can make them efficient on GPUs. (By "efficient" I mean "efficiently exploiting the parallelism", because Wikipedia tells me that bitonic sort has a complexity of O(n × log^2 n), which is more complex than the theoretical minimum for serial algorithms.)