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

java, list, sorting

Solution

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.

Problem

Original source