# 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.