Java Code Review: Merge sorted lists into a single sorted list

Question

I want to merge sorted lists into a single list. How is this solution? I believe it runs in O(n) time. Any glaring flaws, inefficiencies, or stylistic issues?

I don't really like the idiom of setting a flag for "this is the first iteration" and using it to make sure "lowest" has a default value. Is there a better way around that?

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
 List<T> result = new ArrayList<T>();

 int totalSize = 0; // every element in the set
 for (List<T> l : lists) {
  totalSize += l.size();
 }

 boolean first; //awkward
 List<T> lowest = lists.iterator().next(); // the list with the lowest item to add

 while (result.size() < totalSize) { // while we still have something to add
  first = true;

  for (List<T> l : lists) {
   if (! l.isEmpty()) {
    if (first) {
     lowest = l;
     first = false;
    }
    else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
     lowest = l;
    }
   }
  }
  result.add(lowest.get(0));
  lowest.remove(0);
 }
 return result;
}

Note: this isn't homework, but it isn't for production code, either.

Answer 1

To expand on Anton's comment:

By placing the latest result from each List, along with an indicator of whch list it is, into a heap, then continually take the top off the heap, and put a new item on the heap from the list belonging to the item you just took off.

Java's PriorityQueue can provide the heap implementation.

Answer 2

I am not sure, but why don't you directly use a SortedSet instead of List if you want to maintain ordering? Use it instead of the "sorted" lists and you can merge (and automagically sort) them all using Set#addAll().

Basic example which takes unsorted lists:

List<String> list1 = Arrays.asList("foo1", "waa2", "bar3");
List<String> list2 = Arrays.asList("bar1", "foo2", "waa3");
List<String> list3 = Arrays.asList("waa1", "bar2", "foo3");
Set<String> merged = new TreeSet<String>();
merged.addAll(list1);
merged.addAll(list2);
merged.addAll(list3);
System.out.println(merged);

Results in:

[bar1, bar2, bar3, foo1, foo2, foo3, waa1, waa2, waa3]

All using the standard API's

Edit: or is it just homework and/or an exercise? If so, sorry about that, but you should have tagged the question as homework.

Answer 3

Efficiency will suck if lists contains an ArrayList, since lowest.remove(0) will take linear time in the length of the list, making your algorithm O(n^2).

I'd do:

List<T> result = new ArrayList<T>();
for (List<T> list : lists) {
    result.addAll(list);
}
Collections.sort(result);

which is in O(n log n), and leaves far less tedious code to test, debug and maintain.

Answer 4

Your solution is probably the fastest one. SortedLists have an insert cost of log(n), so you'll end up with M log (M) (where M is the total size of the lists).

Adding them to one list and sorting, while easier to read, is still M log(M).

Your solution is just M.

You can clean up your code a bit by sizing the result list, and by using a reference to the lowest list instead of a boolean.

public static <T extends Comparable<? super T>> List<T> merge(Set<List<T>> lists) {
    int totalSize = 0; // every element in the set
    for (List<T> l : lists) {
            totalSize += l.size();
    }

    List<T> result = new ArrayList<T>(totalSize);

    List<T> lowest;

    while (result.size() < totalSize) { // while we still have something to add
            lowest = null;

            for (List<T> l : lists) {
                    if (! l.isEmpty()) {
                            if (lowest == null) {
                                    lowest = l;
                            }
                            else if (l.get(0).compareTo(lowest.get(0)) <= 0) {
                                    lowest = l;
                            }
                    }
            }
            result.add(lowest.get(0));
            lowest.remove(0);
    }
    return result;}

If you're really particular, use a List object as input, and lowest can be initialized to be lists.get(0) and you can skip the null check.

Answer 5

Since Balus and meriton have together given an excellent response to your question about the algorithm, I'll speak to your aside about the "first" idiom.

There are definitely other approaches (like setting lowest to a 'magic' value), but I happen to feel that "first" (to which I'd probably give a longer name, but that's being pedantic) is the best, because it's very clear. Presence of a boolean like "first" is a clear signal that your loop will do something special the first time through. It helps the reader.

Of course you don't need it if you take the Balus/meriton approach, but it's a situation which crops up.