Mergesort a LinkedList

Question

I have made an attempt to write the mergesort routine on a LinkedList in Java. It will be great if somebody can review my implementation and point out the issues with it.

public class LinkedListSort{
    static class Node<T extends Comparable<T>>{
        private T value;
        private Node<T> next;

        public Node(T value,Node<T> next){
            this.value = value;
            this.next = next;
        }

        public T getValue(){
          return this.value;    
        }

        public void setNext(Node<T> next){
          this.next = next;
        }

        public Node<T> getNext(){
         return this.next;
        }

        @Override
        public String toString(){
            if(this.next == null){
              return this.value.toString();
            }else{
              return this.value.toString() +"->"+next.toString();
            }
        }
    }
    private <T extends Comparable<T>> Node<T> getLastHalf(Node<T> list){
        if(list.getNext() == null) return list;
        //Get the last half of the list
        Node<T> current = list;
        Node<T> mid = list;
        int midCounter = 0;
        while(current != null){
            if(midCounter%2 == 0){
               mid = mid.getNext(); 
            }
            current = current.getNext();
            midCounter++;
        }
        return mid;
    }

    private <T extends Comparable<T>> Node<T> getFirstHalf(Node<T> list){
        if(list.getNext() == null) return list;
        Node<T> current = list;
        Node<T> mid = list;
        Node<T> accum = null;
        Node<T> accumPtr = accum;
        int midCounter = 0;
        while(current != null){
          if(midCounter%2 == 0){
           Node<T> fNode = new Node<T>(mid.getValue(),null);
           if(accum == null){
             accum = fNode;
             accumPtr = accum;  
           }else{
             accum.setNext(fNode);
             accum = accum.getNext();   
           }
           mid = mid.getNext();
          }
          current = current.getNext();
          midCounter++; 
        }
        return accumPtr;
    }   

    public <T extends Comparable<T>> Node<T> merge(Node<T> left,
                 Node<T> right){
        Node<T> merged = null;
        Node<T> head = merged;
        while((left != null) && (right != null)){
          Node<T> leftVal = new Node<T>(left.getValue(),null);
          Node<T> rightVal = new Node<T>(right.getValue(),null);
          if(leftVal.getValue().compareTo(rightVal.getValue())<0){
             if(head == null){
             head = leftVal;
             merged = head;      
             }
             else{
                head.setNext(leftVal);
                head = head.getNext();
             }
                 left = left.getNext();     
          }else{
             if(head == null){
                head = rightVal;
            merged = head;
             }
             else{
                head.setNext(rightVal);
            head = head.getNext();
             }
             right = right.getNext();             
          }
        }
        if((left  == null) && (right == null)){
           return merged;
        }
        else if(left == null){
                head.setNext(right);
            return merged;
        }
        else{
           head.setNext(left);
           return merged;       
        }
    }

    public <T extends Comparable<T>> Node<T> 
        sort(Node<T> list){
      assert(list != null);
      if(list.next == null){
         return list;   
      }
      else{
         //Get the first half of the list
         Node<T> firstHalf = getFirstHalf(list);
         //Get the other half of the list
         Node<T> lastHalf  = getLastHalf(list);
         //Sort the first half  
         Node<T> left = sort(firstHalf);
         //Sort the other half
         Node<T> right = sort(lastHalf);
         //Merge the sorted left half and right half
         Node<T> merged = merge(left,right);
         //Return the merged result
         return merged;         
      }         
    }

    public static void main(String[] args){
      Node<Integer> node0 = new Node<Integer>(1,null);
      Node<Integer> node1 = new Node<Integer>(5,node0);
      Node<Integer> node2 = new Node<Integer>(7,node1);
      Node<Integer> node3 = new Node<Integer>(3,node2);
      Node<Integer> node4  = new Node<Integer>(9,node3);

      Node<Integer> node5 = new Node<Integer>(1,null);

      Node<Integer> node6 = new Node<Integer>(2,null);
      Node<Integer> node7 = new Node<Integer>(7,node6);

      LinkedListSort sort1 = new LinkedListSort();
      Node<Integer> result = sort1.sort(node4);
      Node<Integer> result1 = sort1.sort(node5);
      Node<Integer> result2 = sort1.sort(node7);

      System.out.println(result);
      System.out.println(result1);
      System.out.println(result2);
    }
}

Answer 1

An initial few comments:

• You can split your list in one pass, rather than separately getting the two halves. Here's an example of a split method (I lazily used javafx.util.Pair, but you can create your own Pair-like class if you wish).

  static <T extends Comparable<T>> Pair<Node<T>,Node<T>> split(Node<T> list) {
  
    if (list.getNext() == null)
      return new Pair<>(list, null);
  
  
    Node<T> tail = list.getNext();
    Node<T> current = tail;
  
    // Effectively clone
    Node<T> head = new Node<>(list.getValue(), null);
    Node<T> currentHead = head;
  
  
    int midCounter = 0;
    while (current != null) {
      midCounter++;
  
      if (midCounter % 2 == 0) {
        currentHead.setNext(new Node<>(tail.getValue(), null));  
        currentHead = currentHead.getNext();
        tail = tail.getNext();
      }
      current = current.getNext();
    }
  
    return new Pair<>(head, tail);
  }
  

• As a result you'll need to mildly adjust your sort method:

  public static <T extends Comparable<T>> Node<T> sort(Node<T> list) {
    assert (list != null);
    if (list.getNext() == null) {
      return list;
    } else {
      Pair<Node<T>, Node<T>> split = split(list);
      // Sort the first half
      Node<T> left = sort(split.getKey());
      // Sort the other half
      Node<T> right = sort(split.getValue());
      // Merge the sorted left half and right half
      return merge(left, right);
    }
  }
  

• You've used instance methods where static methods would suffice. I would add a private constructor to your class (since no-one needs to construct it) and change all your methods to static methods.

• Minor point: you can defer the creation of leftVal and rightVal until inside the if statements in your merge method:

  if (left.getValue().compareTo(right.getValue()) < 0) {
    Node<T> leftVal = new Node<T>(left.getValue(), null);
    if (head == null) {
      head = leftVal;
      merged = head;
    } else {
      head.setNext(leftVal);
      head = head.getNext();
    }
    left = left.getNext();
  } else {
    Node<T> rightVal = new Node<T>(right.getValue(), null);
    if (head == null) {
      head = rightVal;
      merged = head;
    } else {
      head.setNext(rightVal);
      head = head.getNext();
    }
    right = right.getNext();
  }