You're calculating the average (but incorrectly - it should be /3
, not /2
), not the median.
You should pick the middle element of the three.
Something like: (pseudo-code)
sort(left, mid, right)
pick mid
With your current code, it's likely to end up with a value larger than everything else, so you can possibly end up partitioning off 0 elements to the right, just recursing on the same data towards the left repeatedly.