You are given an array S[1 . . . n] of real numbers, some positive and some negative.

Design an O(n log n)-time algorithm that determines whether S contains two elements S[i] and S[j] such that S[i] = −S[j]. The algorithm returns a “yes” if there is such a pair, and “no” otherwise. If the array S contains the element 0, then the algorithm always returns a “yes”.

Your algorithm has to be in-place (i.e. you can use only constant additional memory).

I solved it using Heap Sort, but is there any other solution? Because it is assumed that the student doesn't know Heap Sort yet.