In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/constant, $O(1)$, sum of $2$ small numbers requires $O(1)$ actions and their size is $O(1)$ bits for representation.
I'd like to analyse an efficient algorithm for this. The algorithm sorts $A$ and then iterates over the endpoints. If their sum is less than $\alpha$, we will check the second smallest element and the largest. If their sum is larger, we will check the smallest and the second largest. So on and on.
This algorithm takes $O(n\log n)$ due to sorting. However, trying to write it as a single-work tape TM, I'm having trouble. Assuming we have $2$ tapes: one read only tape for the input, and another read/write for the working process.
Sorting the array and writing it on the TM takes $O(n\log n) $ by merge sort, using a single tape. However, what about the process itself of comparison?
If we had $2$ tapes, or a single tape with $2$ access heads, we could have done trivially in $O(n)$. But having a single tape seems to be problematic, as I might run back and forth many times, and running back and forth might take $O(n)$.
My question follows: is there a way to implement this algorithm, or any other algorithm for pair-sum, such that it will need $O(n\cdot \log n)$ runtime, on a TM with $2$ tapes: the first is read only and the second is read-write?