Looking for an efficient way to find a sorted order from 2 lists

Question

I have 2 set of unsorted integers: set A and set B. But we don't know how many items are there in setB in advance.

I need to :

while setA and setB are not empty:
    pop the smallest no from setA
    move an int from setB to setA

What is the most efficient way to do that in Java?

I am thinking

1. create an ArrayList for setA and LinkedList for setB
2. while (setA and setB are not empty) sort(setA) pop setA remove an integer from setB and insert in setA

Is there a better way to do this in Java? I would like to remove the 'sort in the while loop' if possible.

Answer 1

TreeSet<Integer> setA = new TreeSet<Integer>(listA);
TreeSet<Integer> setB = new TreeSet<Integer>(listB);
while (!setA.isEmpty()) {
    setA.remove(setA.first());
    if (!setB.isEmpty()) {
        Integer first = setB.first();
        setB.remove(first);
        setA.add(first);
    }
}

Explanation: the TreeSet class maintains the set in a red-black tree that is ordered on the natural ordering of the set elements; i.e. the Integer.compareTo() method in this case. Adding or removing an element finds the appropriate place in the tree for the element, and then adds or removes it without the need to sort.

The isEmpty method is O(1), and the first, add and remove methods are all O(log N), where each has to be called O(N) times. Creating the initial treesets is also O(N log N). So the overall complexity is going to be O(N log N) where N is the total list size.

Answer 2

Here's what I understood from the question: We need one sorted collection that contains all elements from both setA and setB. Because setA and setB may contain equal items, we should use a list (preserves duplicates). If we don't want duplicates, just exchange ArrayList by TreeSet and remove the extra sorting.

I assume, that both sets contain the same type of elements - if not, we can still use Collections.sort but have to push a Comparator to the sort method that is capable of comparing different types of objects.

private Collection<Integer> combineAndSort(Set<Integer>...sets) {
   Collection<Integer> sorted = new ArrayList<Integer>();
// Collection<Integer> sorted = new TreeSet<Integer>();
   for(Set<Integer> set:sets) {
      sorted.addAll(set);
   }
   Collections.sort(sorted); // obsolete if using TreeSet 
}

Answer 3

If you are using Java 5 onwards, consider java.util.PriorityQueue:

Collection<Integer> setA = ...;
Collection<Integer> setB = ...;
if (setA.isEmpty()) {
  // if A is empty, no need to go on.
  return;
}
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(setA);
Iterator<Integer> iterB = new LinkedList<Integer>(setB).iterator();
// no need to check if A is empty anymore: starting off non-empty,
// and for each element we remove, we move one over from B.
while (iterB.hasNext()) {
  int smallest = pq.poll();
  doStuffWithSmallest(smallest);
  pq.add(iterB.next());
  iterB.remove();
}

Note that in the above code, I've first wrapped the setB in a linked list to support efficient removal. If your setB supports efficient removal, you don't need to wrap it. Also note that since you don't care about moving elements from the front of setB, an ArrayList can support very efficient removal:

private <T> T removeOne(ArrayList<T> array) throws IndexOutOfBoundsException {
  return array.remove(array.size() - 1);
}