Package Idea: Sorting

[RianGoossens]

Sorting is ubiquitous in software, but kind of tricky to get right on GPU. It would be very useful to have this as a package, for example to write a raytracer.

There's a lot of research out there, a good place to start would be https://developer.nvidia.com/gpugems/gpugems2/part-vi-simulation-and-numerical-algorithms/chapter-46-improved-gpu-sorting

We probably need at least a regular sort and an argsort.

Cubecl traits would be a nice way to implement this, being able to swap out sorting algorithms easily. This would also making testing easier.

• odd-even transition sort
• odd-even merge sort
• bitonic merge sort
• radix sort
• other sorting networks?

[nathanielsimard]

great idea!

[AsherJingkongChen]

How about Radix Sort? It is quite fast for u32 keys.

[RianGoossens]

How about Radix Sort? It is quite fast for u32 keys.

Oh I had no idea radix sort was possible on gpu's! I've gotten some algorithm's to work already on cubecl, will check if I can port this too!