Q:

Merge many unsorted lists efficiently

I have many huge unsorted List containing (user,amountspend) tuples. Each list corresponds to one day.
Now I want to merge the all the list to have one list which contains accumulated value for a given user. I have two approaches:

Approach 1: Sort the individual lists and then use merge sort iteratively.
Approach 2: Form a HashMap with user as key and then iterate through list 
and update the value for key if it exist or add a new key with value.

If m list are there and each list may have different length (k1,k2,...,km)
Questions:
Which is efficient solution?
Which solution can be run in multiple threads?
Or is there any better solution?
Example:
Day 1: (user1,100),(user2,200)
Day 2: (user2,10),(user1,100),(user3,10)
List after merging: (user1,200),(user2,210),(user3,10) 

A:

1 Overall approach and complexity
I suppose:

number of client is large but finite = N
number of days keep growing = M
and perhaps each day, we have every client (or almost that).

Minimal complexity to do the job:

process each data, so M.N operations. As you dont want to keep elements for the sum, you only need to do:
partial sum + new value, so, everything takes M.N x finite time (I suppose you dont have billions of billions of billions of $)
you have to agregate datas, on N clients (and for each data, you have to find, sum, store, ... on each client).
For me, minimum time is to sort the clients at least once (or any method to index them),
so time to do that is O(N log N) with the best algorithms and best
implementations (there exists also faster ways, but with very huge amount of space).

So, you need at least O(N log N) + O(M.N).
2 possible solutions:
Your approach 1 wastes time: because you sort every list (with one same data).
You would need M.O(N log N)+O(M.N). 
You only need one sort (to be able to sum after).
Your approach 2 is the shortest way.
3 How to parallelize ?
You have (at least) 2 ways to split your datas: with days, or with clients. Because you want to sum on clients, use
the second.
Your process is easy scalable.
Then you can use a simple hash function (first or last character of client, or something very simple) 
=> each thread (or process, or machine) receives every datas, and keep only datas for its clients.
You can split every job like that (process, sum, retrieve, ...).
If will take almost same overall time:
with k process, you will have k.O (N/k log N/k)  + k*Ox(M.N) + k.O(M.N/k)
The time you win by splitting N/k, you give back by selecting (Ox, I suppose very fast).
Then you can distribute your job on many machines, which will be independent.
Hope it helps.

