looking for algorithm to calculate h-index fast

Answer in c# but easily convertable to java as well

    public int HIndex(int[] citations) {
            Array.Sort(citations);

            var currentCount = 0;
            var length = citations.Length;
            for (var i = citations.Length - 1; i >= 0; i--)
            {
                currentCount = length - i;
                // if the count of items to the right is larger than current value it means thats the max we can expect for hindex

                if (currentCount - 1 >= citations[i])
                {
                    return currentCount - 1;
                }
            }

            return currentCount;
    }

Here my realization O(N) with tabling, this is simple and blazing fast:

private static int GetHIndex(int[] m)
{
    int[] s = new int[m.Length + 1];
    for (int i = 0; i < m.Length; i++) s[Math.Min(m.Length, m[i])]++;

    int sum = 0;
    for (int i = s.Length - 1; i >= 0; i--)
    {
        sum += s[i];
        if (sum >= i)
            return i;
    }

    return 0;
}

This could be done in O(n) time.

1. Find median of the array.
2. if median > (n-1)/2 then the number comes before median. Find it iteratively
3. If median < (n-1)/2 then the number comes after median. Find it iteratively.
4. If median == (n-1)/2 then the median is the solution

Here I am assuming that n is odd. Change algorithm slightly for even n (replace (n+1)/2 with n/2 assuming rank of median is n/2). Also, finding actual median in O(n) time is complicated. Use a good pivot instead (as in quicksort).

Complexity: n+n/2 +n/4... = O(n)