Introduction to GPU Radix Sort
Takahiro Harada, Lee Howes · 2011
The prefix sum is the sum of all values in preceding locations in the sequence: in this case those to the left of the current location. In the case of the radix sort this means that the prefix sum computes the total count of all values less than the current value. For example, the prefix sum of location, and hence value, 2 is o2 = 3. This means there are 3 entries for 0s and 1s in the sequence. Thus, 3 is the destination address of the first 2 in the data set. The destination address of an element is the sum of the offset computed via the prefix sum and the index of the value in the set of the same value in the original array: the second 2 in the array would be at location 3 + 1. The elements are shuffled by calculating the destination address to get a sorted array.