Jim Driscoll's Blog

Notes on Technology and the Web

Combining two sorted lists

leave a comment »

As another interview question, let’s tackle the idea of sorting two sorted lists. While we’re at it, let’s discuss a few factors outside of the basic question being asked.

The question is: “Given two sorted lists, combine them into one sorted list”

Now, of course, that’s really easy in Java:

    private static List naiveListSort(List first, List second) {
        List combinedList = new ArrayList(first.size() + second.size());
        return Collections.sort(combinedList);

…but that’s probably not what your interviewer had in mind. They’d like it to be faster. (This will sort two 20 million item lists in 2.5 seconds, but hey, always room for improvement.)

OK, let’s use Streams:

    private static void sortStreams(List first, List second) {
        Stream random1 = first.stream();
        Stream random2 = second.stream();
        Stream combined = Stream.concat(random1, random2).sorted();
        return combined.collect(Collectors.toList());

That returns two 20 million item lists in 2.3 seconds. Still want it faster?

Well, depending on what you’re doing, you can just return a Stream instead of a List, that shaves off a pretty big chunk of time – it’s about 1 millisecond or so, since the sorting is done lazily. Running an operation like .count() on it works in 1.9 seconds. But that’s probably not what’s meant either. What they really mean is they want you to do it the hard way – take advantage of the fact that the two lists are already sorted, and use that to eke out a little more speed:

List combinedList = new ArrayList(first.size() + second.size());

int i = 0; // first index
int j = 0; // second index
int firstsize = first.size();
int secondsize = second.size();
while (i = second.get(j)) {
        if (j >= secondsize) {
    if (j >= second.size()) {
if (j < second.size()) {  // add remaining
    combinedList.addAll(second.subList(j, secondsize));
} else if (i < first.size()) {
    combinedList.addAll(first.subList(i+1, firstsize));

That delivers results in 1.7 seconds. Total savings over the Stream version, .6 seconds! That's a savings of about 25%!

This is also the best case scenario for the naive functions – the comparison operation can literally fit into a single assembly instruction, and thus executes lightning fast. As the complexity of the comparison goes up, the difference in execution times does too. So, the improvement for other sorts (such as on String alphanumeric order) will be even larger.

But look what you gave up by doing this the fastest way:

  • It's now more fragile – if you pass it unsorted data, it will pass back even more unsorted data. A single out of place value causes a severe failure.
  • It's harder to read and maintain, meaning that at some point, it will cost precious manpower if you need to modify it in any way. And it will need to be tested – it's all too easy for a small bug to make it's way in.
  • Also, if you want the result to be a Stream, you have to convert it back (and from what I've seen so far of Streams, their use is going to become extremely common). But that last point is prehaps a bit unfair.

Still, the likelihood of needing the last method is somewhat remote, unless you're writing framework software or a database. The likelihood of needing one of the preceding methods is pretty good. (As a framework developer, I still write more code that looks like the first version than the last. It's all about the critical path.)

So, if you're interviewing a candidate, I'd suggest that the answer you're looking for is probably one of the first ones, rather than the last one. While your candidate should certainly be able to program the last one, they should also have to wisdom to know that it's almost never necessary – and why. Good answers would include such phrases as: "Is this in the critical path?", "What's the user expectation for response time?", and "How robust does this have to be? Can I trust the inputs?"

If you're interested in the complete code (including the surrounding code which tests performance, in a fairly primitive manner), see the gist.


Written by jamesgdriscoll

January 2, 2014 at 5:39 PM

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: