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.