Merging a collection of unsorted arrays to find common elements

Question

How different would it be to merge a collection of unsorted arrays type Comparable versus the code below?

Comparable [][] collections {colA, colB, colC};

After searching I found a way of merging two sorted array of primitive data.

public static int[] merge(int[] a, int[] b) {

int[] answer = new int[a.length + b.length];
int i = 0, j = 0, k = 0;
while (i < a.length && j < b.length)
{
    if (a[i] < b[j])
    {
        answer[k] = a[i];
        i++;
    }
    else
    {
        answer[k] = b[j];
        j++;
    }
    k++;
}

while (i < a.length)
{
    answer[k] = a[i];
    i++;
    k++;
}

while (j < b.length)
{
    answer[k] = b[j];
    j++;
    k++;
}

return answer;

}

Here, How to merge two sorted arrays into a sorted array?

Assuming that I have K arrays (e.g. A & B...), and I want to obtain list C (allowing duplicate items). I want to only compare each element one time. For faster performance even if I compromise on memory.

Thank you!

amit · Answer 1 · 2015-09-24T18:30:25.073

1

If you have k sorted arrays, and you are looking to merge them, you can build a heap (PriorityQueue), that at the beginning is populated by the first element from each list.

Then, until the queue is empty:

Pop the lowest element from the queue
Append the element to the sorted merged list
Add to the queue the next element in the list where the popped element belonged to (if such exists).

This is done in O(nlogk) time, where n is the total number of elements and k is the number of lists. It is easy to show this solution is optimal, because otherwise you could sort an unsorted list better than Omega(nlogn)

edited Sep 24 '15 at 18:30

answered Sep 24 '15 at 18:03

amit

175,853
27
231
333

To me it seems that step 2. seems to be O(k), leading to O(nK), because the elements in the queue are not sorted. What did I miss? – A.S.H Sep 24 '15 at 18:13
Good method though, I doubt we can find better. My question meant that each time an ekement is added to the PriorityQueue, we have to find the minimum of k unsorted elements. (please read step 1. instead of step 2.) – A.S.H Sep 24 '15 at 18:18
1

@A.S.H It's a priority queue/heap. it's sorted to find the minimal value in O(1), insertion and extraction of minimum in O(logk) – amit Sep 24 '15 at 18:29
@amit How can I make this faster? So that each element only gets compared one time. – sag_dc Sep 25 '15 at 03:16

score 0 · Answer 2 · answered Sep 24 '15 at 18:56

0

You can use essentially the exact same algorithm you listed. The efficiency is O(nk^2), so it's not optimal but it'll be easy to implement since you already know how to do it for k=2.

answered Sep 24 '15 at 18:56

Orch

887
2
8
21

Merging a collection of unsorted arrays to find common elements

2 Answers2