Parallized algorithm for getting the frequencies of numbers in an array I have an array $A$ of length $n$, containing integers between $0$ and $n-1$ inclusively. I would like to convert this to an array of frequencies $F$, that is, $F[i]$ should be the number of times $i$ appears in the array $A$. For example, $A=[1,3,1,1,0]$ would be mapped to $F=[1,3,0,1,0]$. There is an easy algorithm for this, however I would like to do this efficiently in parallel. Here is my first attempt at doing so:
Let $n = p*k$ where $p$ is the number of threads, $k$ is the number of indices each thread will process and $n$ is the total number of indices (length of A). Each thread is given a range containing $k$ indices and all threads have access to an array $F$ that will be the frequency list. $F[i]$ starts off containing $0$ but after successfully running the algorithm, will contain the frequency of index $i$ in the array $A$.
Each thread runs the following pseudo code:
for i in given range:
  F[A[i]] += 1

Assuming a mutex is used, I think this algorithm works fine, however it runs into efficiency problems because all threads may want to increase the same index of $F$ at the same time. For example, this would happen if every index of $A$ contains the same number.
I would like an algorithm which avoids this problem and is deterministic. Ideally the time complexity should be something like $O(n/p)$. This is probably not possible of course, but I would like to be able to take at least some advantage of the parallelism, even when assuming a worst case input.
It is common problem in parallel computing. Many parallel framework have &quot;reduction operator&quot; for such processing. Idea is simple.
Use separate local copies of F[A[i]] in each threads. Calculate frequency in parallel for each sub-array block in parallel. Now since each thread is updating only its local copy of frequency array F[A[i]], no mutex is required. After the completion of all threads, join all the per thread F[[A]] array's into a single application array, i.e., reduce. You will get almost O(n/p) time complexity. The actual time complexity will depend on Size of your array (larger, the better) and the number of threads (creating and joining threads takes time).