Adobe Interview Question Software Engineer / Developers
0of 0 voteshow will you sort a file which is too large?
lets suppose memory has M blocks and you want to sort B blocks. Then you can pull M blocks into memory and sort them and write output to disk. This will take B/M steps.
Now pick the first block of each of (B/M) blocks written previously and merge them and write them to disk. If B/M > M, then you will need to repeat the process to till all the blocks are sorted. Now merge the sorted blocks and repeat.
Visualize like a tree structure.
No you wont require M blocks of memory for merging. All you have to do is read from say 2 blocks like a stream and write the output to the disk immediately. You continue this until there is no data left in blocks to read further.
suppose its a 900 mb file and our ram is 100 mb... i.e. 9 blocks
1. bring each block in ram and sort (O(nlogn)) and then put back
2. now we have 9 consecutively sorted blocks.
3. maintain an input buffer of 90 mb and output of 10mb
4. get 10 mb each from start of each block i.e. toal 90mb in input buffer.
5. perform 9-way merge into 10mb output buffer.
6. whenever o/p buffer is filled, write it to disk and erase from ram
7. whenver either of 9 chunks are all read, copy futer 10 mb from the corresponding 100mb block until it exhausts the 100mb
8. do this until all chunks are processed.
source:wiki
External sorting with merge sort.
- S September 15, 2010