Java Code Review: Merge sorted lists into a single sorted list [closed]

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

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.