Sort a LinkedList? Revisiting Insertion Sort in Java

In a previous post, I showed a possible implementation of insertion sort written in Java. The code is an almost verbatim translation of pseudocode from CLRS.

Almost verbatim. While the pseudocode doesn’t include any type declarations, my Java code does. Specifically, I chose to work with a LinkedList, since a data structure that allows for easy insertion and deletion of elements felt like a natural fit for an algorithm named insertion sort. The code ended up looking like this:

public LinkedList<Integer> mySort(LinkedList<Integer> list) {
    for(int j = 1; j < list.size(); j++) {
        int key = list.get(j);
        int i = j - 1;
        while(i >= 0 && list.get(i) > key) {
            list.set(i+1, list.get(i));
            i = i - 1;
        }
        list.set(i+1, key);
    }
    return list;
}

Now imagine my dismay when I read this post about how to succeed in an interview at Google. Specifically, note his comment about my chosen data structure: “For God’s sake, don’t try sorting a linked list during the interview”.

Don’t try sorting a linked list during the interview? I just tried sorting a linked list on the internet. My tests said that the algorithm worked, too; what was I doing wrong?

Upon deeper investigation, I found some virulent criticism of the linked list, and decided it was time to revisit my implementation of insertion sort, taking note of a few things:

– Retrieving elements from a linked list by index, it turns out, is computationally expensive. Specifically, the .get() operation I use to access values is an O(n) operation; since a LinkedList is a sequential access list, accessing elements by index takes linear time (i.e. you have to traverse all prior elements in the list until the desired index is reached).

By contrast, .get() is an O(1) operation for an ArrayList; elements can be accessed by index in constant time since this data structure is a random access list.

– My algorithm doesn’t actually require inserting and deleting elements. Though the name “insertion sort” might suggest otherwise, what’s really happening is that values are being swapped (replaced, rather than inserted and deleted). An ArrayList excels with .get() and .set() methods, while a LinkedList excels with .add() and .remove() — and I’m only using the former pair!

So in the interest of performance, I decided it might be better to use an ArrayList. That’s a quick fix: just change the method return and parameter types from LinkedList<Integer> to ArrayList<Integer>.

But, upon reflection, even this data structure felt unnecessary. I don’t need to dynamically modify the size of the input, so I can just work with a simple array.

That code now looks like this:

public int[] mySort(int[] list) {
    for(int j = 1; j < list.length; j++) {
        int key = list[j];
        int i = j - 1;
        while(i >= 0 && list[i] > key) {
            list[i+1] = list[i];
            i = i - 1;
        }
        list[i+1] = key;
    }
    return list;
}

… and it works just fine.