Don wrote:
BCS wrote:
in sudocode
1. build a min heap out of the elements based on the first element of
each array
2. remove the first value from the root of the heap,
3. if empty array, drop it
4. if not empty re-heap
5. goto 2 if anything left
In practice, I bet it'll go faster with a couple more steps:
2. remove the first value (from array X) from the root of the heap,
2a. Determine new root of the heap (don't need to do a full re-heap yet).
2b. move all values from X until empty or >= new root.
4. reheap
Correct. Unfortunately my heap primitives didn't quite allow that so
currently I do it the "hard" way: pop from top, remove top from heap,
reinsert (if not empty). But this is definitely an optimization worth
doing. I think I'll implement it.
There are interesting cases like:
[5,6,7,8,9,9,......9]
[30, 31,32,33,34...38]
[1,1,1,1,1,1,1,1,1,1,...1]
[10,11,12,13,14,15,16,16,......., 16]
where in theory, the total number of comparisons required is a function
only of the number of arrays, and is independent of the actual number of
elements.
If it's common to have runs where consecutive values come from a single
array, and the arrays are random access, you could do MUCH better than
O(n).
I think you can't do better. Complexity is O(n) at a minimum because you
need to go through each element. The heap-based algorithm has O(n log
m). What you could improve on is the log m factor (m = the number of sets).
Andrei
