Step Complexity of thrust sort and thrust unique by key

Question

I was just wondering what is the step complexity of the thrust::sort function and what are work and step complexity of the thrust::unique_by_key function.

Based on my knowledge, I think the work complexity of sorting is O(N log N). But I have no idea what it is for the unique_by_key operation.

Answer 1

There are two types of sort in Thrust. There is a radix sort and a comparison sort. For radix sort, the work complexity is O(kN), where N is the number of keys and k is the key length. For comparison sort, the work complexity is O(N log N), as you mentioned.

unique_by_key is a stream compaction operation, which means that work complexity is O(N).