Finding complementary pairs
This is not O(n log n) algorithm, because this part is quadratic:

  for (var i = 0; i &lt; firstArray.length; i++) {
    for (var j = 0; j &lt; secondArray.length; j++) {
      if (firstArray[i] + secondArray[j] == k) {
        count += 2
      }
    }
  }


Denoting n = input.length, this has roughly (n/2)^2 = n^2/4 steps, which is O(n^2).

The rest of this answer is a result of a misread and is not directly related to the question. I'll leave it as a comment of a possibly extended exercise.

However, I'm not sure that O(n log n) algorithm does exist. Consider

a = [ 1, 2, 4, 8, ..., 2^n ] (for some n)


and k is a sum of all elements in a. Since you can repeat the numbers, and a[k] = 2*a[k-1] for all positive k, you'd have exponential number of sums, so no O(n log n) algorithm will solve this.

It is easy to show that the number of solutions is strictly bigger than 2^n. Just note that

k = (sum of ANY elements in a except a[0] = 1) + (sum of the remaining elements in a) * 1.


The first sum can be chosen in 2^n ways. Of course, there are other sums as well, but this is enough to show that you can have an exponential number of solutions, which is enough to show that no sub-exponential algorithm can find them all.

Of course, there may be a mathematical trick to compute only how many such solutions there are, but I don't know it.