Does my solution converge to O(N) for worst-case time complexity?
$ \sum_{i=1}^n \frac{i}{n} $ is the harmonic sequence, which goes to $\log(n)$

since in your question you claim the $T =\frac{n}{2} \sum_{i=1}^n \frac{i}{n}$ 

$T = \frac{n}{2} \log(n) = O(n\log(n))$