Consider the following problem. Does a given input set of n integers {x1, x2, . . . , xn}, contain three elements that sum to zero? In the search version of the problem, the correct output is a set of three indices {i, j, k} such that xi + xj + xk = 0 if such a set exists, and No otherwise.

Show that by sorting the input, you can speed up your algorithm to obtain an algorithm that runs in O(n 2 log n) time.