CareerCup

We will have a cluster of hosts, each host having some numbers. Then, we use parallel quick sort. Use MPI programming in C, to quick sort the numbers using MPI communication mechanisms.

Using a bunch of servers to store all the numbers. If all the numbers are within a specific range, we can use bucket sort which is pretty fast. Also external merge sort is a good idea.

I think the best solution for this situation is to scale horizontally and make use of GPUs. At a speed of 10 million inputs (* sizeof(int) to get an idea about memory) each 4 s, 20 machines could sort that 1pb of data in between 2 to 4 days.

Assuming sizeof int is 4 bytes, to store all possible integer numbers would cost just 34 GB storage. So 1 Peta Byte of numbers should have lot of repetions. So device a number map table in an 1 TB harddrive with following mapping:

<Number, NumOccurrances> table should have 2^32 entries with NumOccurrances set to Zero initially. Start reading the hard drive where unsorted numbers are stored. And as the numbers are read increase the corresponding NumOccurrances instance in the table. Just to ensure that the NumOccurrances does not overflow, pick that as 64 bit long integer.

This solution works assuming integer size is 4 bytes. If the size taken is more than 4 bytes, alternative approach need to be taken as our above assumption will not longer hold good