Insert sort on a linked list

Question

I want to do insert sort in a linked list without using dummy nodes.

This is my code. How can this be improved? Any input is appreciated.

public static Node insertSort(Node node){

   Node sortedList = null;
   while(node != null){
    Node current = node;
    node = node.next;
    Node x;
    Node previous = null;
    for(x = sortedList; x != null; x = x.next){
        if(current.value < x.value){
                break;
         }
         previous = x;
    }
    if(previous == null){               
          current.next = sortedList;
          sortedList = current;
    }
    else{               
       current.next = previous.next;
       previous.next = current;
    }
  }
  return sortedList;
}

Answer 1

Algorithmically, your implementation seems fine. One improvement would be to initialize the sortedList to the first node right away. This necessitates some error checking up front, which I think is better style anyway.

I would also run a check for the current node being the new sorted head first. That way I can automatically assume that I'm inserting after the search position. That allows elimination of the previous variable.

But this is all stylistic stuff to make the logic flow easier to understand. As I said, I think your implementation functions perfectly well.

public static Node insertNode(Node node) {
    if (node == null)
        return null;

    // Make the first node the start of the sorted list.
    Node sortedList = node;
    node = node.next;
    sortedList.next = null;

    while(node != null) {
        // Advance the nodes.
        final Node current = node;
        node = node.next;

        // Find where current belongs.
        if (current.value < sortedList.value) {
            // Current is new sorted head.
            current.next = sortedList;
            sortedList = current;
        } else {
            // Search list for correct position of current.
            Node search = sortedList;
            while(search.next != null && current.value > search.next.value)
                search = search.next;

            // current goes after search.
            current.next = search.next;
            search.next = current;
        }
    }

    return sortedList;
}

See it run in JavaScript: http://jsfiddle.net/2LDGD/2/

Answer 2

well sry, i dont have much time to read your code but one of the best ways i used in such problems is to create a "swap function", that uses in every sort algorithm, then you can implement every algorithm you want and change the swap function with yours and of course custom traverse commands