Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array Given an integer array $a$, create a function, $\text{int} \; \text{pairs}( \text{int} \;a[\;])$ that returns the number of equal element pairs in the array. For example, given the array $a=[2,5,1,2,5,1,1,6]$ the pairs are $(2,2), (1,1), (1,1), (1,1)$ and $(5,5)$, so the function should return $5$. The solution needs to run in $O(n \log n)$ time and $O(n)$ space.

My algorithm first sorts the array using  quick sort in $O(n \log n)$ time, then go through the sorted array and for each chunk of equal elements, keep track of the size of the group(which resets to $1$ when a distinct element is next), runs in $O(n)$ time. 

If the next element equal the previous element, then increase the group size variable. 

Otherwise, if the group size variable is bigger than $1$, add $n \choose 2$, where $n$ is the group size, to the overall sum of pairs variable(initially $0$), then reset the group size variable to $1$.

The problem I have is that, although the algorithm is correct, the algorithm runs in $O(n^2)$, which I think is because of the $n \choose k$ method.

The pseudo-code for my $n \choose k$ method is:

int binomial(n,k)
    if(k&gt;(n-k)) k=n-k

    int b=1
    for(int i=0, m=n; i&lt;=k; i++, m--)
        b=b*m/i

    return b


If the method does run in $O(n^2)$, then can I modify it to make it $O(n \log n)$. If its not possible to make a binomial coefficient method to run faster than $O(n^2)$, then does anyone have another algorithm for achieving the number of pairs from the array.
Just evaluate $\binom k2$ with $\frac{k(k-1)}2$, this takes $O(1)$.



Note that if the pairs are to be counted "without replacement", the formula is $\lfloor\frac k2\rfloor$.