Scalable NativeSort

Right now i’m using Unity.Collections Sort extension to sort a native array in a IJob but that is not scalable and it becomes a bottleneck when i have to sort >30k elements.
How could i have parallel sorting using parallel jobs? Is this even a good idea?

2 Likes

Thanks!
That is a nice piece reading.
I might end up not needing parallel sorting but only selection sort for the highest N elements.

1 Like

I’m doing some heavy sorts myself. I start with a single IJob that bins the values into buckets of different ranges. Then I dispatch a parallel job to sort each bucket. And the finally I have a job that appends the buckets back to a single array. For buckets, I use NativeLists.

I am also sorting a single float value and consequently found that a radix sort is about 2.5x faster than Unity’s generic sort.

2 Likes

I’ve ended up doing this:

  • Slicing the unsorted array in N slices(where N is cpu cores - 1) in one IJob

  • Sort those slices in parallel using Unity Native Sort

  • Merge them back into the final sorted array

I’ve managed to sort ~2 times faster than with Unity Native Sort with IJob.

1 Like