How do I work out the recurrence relation of the given function?
In the following I won't pay much attention to floors, celings, and &quot;off-by-one&quot; errors since they won't ultimately matter in the analysis of the recurrence relation. However all of the following calculations can be made precise.
If $n = \texttt{high} - \texttt{low}$ then $\texttt{gap} = n/5$ and the algorithm will perform three recursive calls:

The first on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{low}$ and $\texttt{low}+2\texttt{gap}$.
The second on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{low}+ \texttt{gap}$ and $\texttt{low}+3\texttt{gap}$.
The third on the $2 \texttt{gap} = 2n/5$ elements between $\texttt{high}- 2 \texttt{gap}$ and $\texttt{high}$.

Also notice that when $n = O(1)$ then the time complexity of the algorithm is constant, and that the time spent in the non-recursive parts of the algorithm is also $O(1)$.
The recurrence relation is then:
$$
T(n) = 3T\left( \frac{2}{5} n \right) + O(1),\\ \quad T(1)=O(1)
$$
which can be solved...

 using the Master theorem to yield $T(n) = O(n^{\log_{5/2} 3}) = O(n^{1.1989\dots})$.