twoSum Algorithm : How to improve this?

Sort the array. Make two pointers point at first and last (x and X). Run this in a loop:

if      (a[X]+a[x] >  N) then X-- 
else if (a[X]+a[x] <  N) then x++
else if (a[X]+a[x] == N) then found.

if (x > X) then no numbers exist.

O(nlogn) time, O(1) memory

O(n log n) time, O(1) memory (not counting the list):

1. First, sort the list. This should take O(n log n) time, as most sort functions do.

2. Iterate through the list, which should take O(n) time in the outer loop. At this point you can do a binary search for the closest matching integer in a sorted sublist, which should take O(log n) time. This stage should wind up taking O(n log n) total.

Edit: Check out Max's answer below. It's still O(n log n) time and O(1) memory, but he avoids the binary searches by walking a pointer from each end of the list.

O(n) time, O(n) memory:

Build a hash table, which should have O(1) insertion and O(1) contains. Then, in a O(n) outer loop, for each number i, check if total - i is in the hash table. If not, add it; if so, then you've got your two numbers.

Either way, you would need an additional scan through the array to get the indices, but that's no problem--it only takes O(n) time. If you wanted to avoid it you could keep the original index in the sorted list or hash table as needed, but that has a memory footprint instead of a time footprint.