CareerCup

One example of external sorting is the external mergesort algorithm.[1][2] For example, for sorting 900 megabytes of data using only 100 megabytes of RAM:

   1. Read 100 MB of the data in main memory and sort by some conventional method, like quicksort.
   2. Write the sorted data to disk.
   3. Repeat steps 1 and 2 until all of the data is in sorted 100 MB chunks, which now need to be merged into one single output file. The idea of external sorting is divide and conquer.
   4. Read the first 10 MB of each sorted chunk into input buffers in main memory and allocate the remaining 10 MB for an output buffer. (In practice, it might provide better performance to make the output buffer larger and the input buffers slightly smaller.)
   5. Perform a 9-way merge and store the result in the output buffer. If the output buffer is full, write it to the final sorted file. If any of the 9 input buffers gets empty, fill it with the next 10 MB of its associated 100 MB sorted chunk until no more data from the chunk is available.

As phone numbers are unique, we can use bitmap for representing them.

Assuming a phone number is of 10 digits, 10^10 numbers are possible (in fact many of these are invalid phone numbers. But, for simplicity, lets consider them too.)

So, we need, 10^10 bits to represent them. It's around 1 GB.

In first pass, we can set the corresponding bit to 1. And then in the second pass, read the array of bits and write them back to the file.

external sort

@cac.
Can you explain external sort more..

External sort.
Also modified merge sort should work.