1
$\begingroup$

What algorithm should be used here to solve this problem efficiently?

One file stores 5 year log of user IDs & their website visit dates in random order. There were around 1,000,000 users on the website and 1/4 of them were active. Active users visited the website 100 times a day on average.

You need to create a new file in which user IDs would be sorted in ascending order. For the same user IDs records should be sorted by their visit date in ascending order.

Input example:

1234567890 2013-03-08 12:26:09
0987654321 2013-03-09 09:23:17
1234567890 2014-01-01 00:00:34
0087645544 2015-02-03 17:45:01
0087645544 2015-01-03 11:05:06

Output should be:

0087645544 2015-01-03 11:05:06
0087645544 2015-01-03 17:45:01
0987654321 2013-03-09 09:23:17
1234567890 2013-03-08 12:26:09
1234567890 2014-01-01 00:00:34

What I've tried so far:

From what I've yet found out, the External Sort algorithm should be used here. But how exactly, there are different types of it (2-way, k-way etc)? And how do I apply it to the second column (which is visit date)?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Jan 9 '18 at 23:30
  • $\begingroup$ This needs more context: without being in the same course, we can't guess what is meant by The External Sort algorithm. $\endgroup$ – reinierpost Jan 10 '18 at 9:43
3
$\begingroup$

I suppose the file is too large to fit in the main memory at once. In this case a basic solution is to divide the file into small enough parts so that you can sort each part individually in memory using any standard sorting algorithm. You can then merge the parts by placing a pointer to the start of each file and repeatedly advancing the pointer with the smallest element, collecting the elements into one big sorted file (you can keep track of the minimum using a heap data structure). This is called a $k$-way merge, where $k$ is the number of parts. If the heap does not fit into the main memory, then we can merge just $k' < k$ files at a time, and then merge $k'$ of the merged files at a time, then merge $k'$ of those, and so on, until only one file remains.

I think this is more or less what the Linux sort command does for large files. It can also handle keys consisting of multiple columns. Check the manual of the program for the details.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.