Interestingly, this can be done in sublinear time for a sorted array with a frequent mode—the fact that the array is sorted lets us skip over a bunch of elements.

Suppose we have a sorted array of [math]n[/math] integers with (unknown) mode frequency [math]m[/math]. Let [math]2^k[/math] be the largest power of [math]2[/math] less than [math]n[/math]. Start by sampling every [math]2^k[/math]th integer in the array, then every [math]2^{k-1}[/math]th, every [math]2^{k-2}[/math]th, etc. until we find two integers at distance [math]2^i[/math] that are equal. Since the largest distance between two equal integers is [math]m - 1[/math], we must have [math]2^i < m < 2^{i + 2}[/math].

At this point, the mode must be one of the [math]\bigl\lceil\tfrac{n}{2^i}\bigr\rceil[/math] integers we’ve sampled. Use binary searches to find the left and right endpoints of the intervals equal to each of the sampled integers. The longest such interval will be the mode.

The total runtime is [math]O\bigl(\tfrac{n}{2^i} + \tfrac{n}{2^i}\cdot i\bigr) = O\bigl(\tfrac{n(1 + \log m)}{m}\bigr)[/math].