Find two integers with the largest sum within a budget (breaking ties by smallest difference)
To change your algorithmic order, say from N^2 to N lg N, you must change your algorithm. A simple change will not suffice. But I can think of a better algorithm:

Let us accept the theorum that for each number x in your list, you have a number y such that x + y = z and no other y for the given x will produce a z' where z &lt; z' &lt; budget. That is to say, y is the perfect match for x.

We can use a binary search to find the best y for a given x once the array is sorted.

We can find the y for each x in the array, and the corresponding z. We can loop over these results to find the highest z that does not break the budget, assuming one exists.

The actual code is left as an exercise to the reader, but I think there should be sufficient details to craft it, considering you understand the problem enough to have created a naive solution.