What type is this sorting algorithm?

Question

I needed to sort vertices into buckets as an optimization for collision detection later. I came up with this:

1. Go over all the vertices and count the size that each bucket needs to be to contain them into an array.

2. Shift the size array index by -1 unit and use it as offset array instead.

3. Create a single array for all the indices, go over all the vertices again and place their indices according to the offsets while bumping the offset each time.

4. Use the index list to translate vertices to their new positions (or optionally move the vertices on step 3 if you don't need a map but I did for transforming other primitives).

Surprisingly enough, it's much faster than std::sort (by 10x) or a gpu bitonic sort (by 13x) that I implemented earlier. It can't be a new idea since it's so simplistic in its concept. So what is it called? I want to see what other people have done with it to perhaps make it even faster.

Answer 1

This is known as counting sort. On a domain of size $d$, counting sort runs in time $O(dn)$, compared to $O(n\log n)$ of comparison-based sorts. When $d\ll\log n$, i.e., when the domain is small compared to the total number of elements, we would expect counting sort to be faster. Counting sort can even be iterated, and this is known as radix sort.

If $d = o(\log n)$, then counting sort runs in time $o(n\log n)$, which might seem to contradict the well-known $\Omega(n\log n)$ lower bound on sorting. There is no contradiction, however, since the lower bound only holds for comparison-based sorts, which counting sort evidently isn't.