title: Smallest Largest Sum of Paired Array
body: <p>I have an array of integers which has even length. As an example, letš take an array <code>{0, 6, 4, 22, 19, 11}</code>. Pairing all the numbers into pairs, I have to find the largest pair sum. Now, out of all possible combinations I must find the case when the largest of pair sums is the smallest.
  In this case it would be 23 (when the pairs are 0-22, 4-19, 6-11).</p>
  
  <p>Now the only case I can think of is checking for every possible set of pair sums, finding the largest pair and checking if it is smaller than the last time. This, however, is incredibly inefficient as it requires looping through the array as much as it's length squared times. I am wondering if there is any more efficient way to do it.</p>
  
  <p>I am considering that sorting the array and finding the largest sum choosing pairs from the first and last elements, then moving inwards, could work, but I am not sure if this is true in all the cases.</p>