Searching and sorting in a 2-d array

Suppose you have a 2-d array with integers sorted both horizontally and vertically.
a) Search for the occurrence of a value in the array
b) Sort the array into a single-dimensional array

Sorting for large data sizes

I have a computer file containing 1,000,000 non-negative integers, in no particular order. Imagine that they are the membership numbers of people who are enrolled in my internet club. A new person wants to join the club, and we need to find an unused number to allocate to them. How would you find, in a reasonable time, a number that was not already in the file?

Hint: Use Selection trees for finding the first missing integer among those 1,000,000 integers. The in memory amount of data that we have to keep is very small.

Reference: http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch6.html