5
\$\begingroup\$

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);
    }
}
\$\endgroup\$
2
\$\begingroup\$

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();
    }
    
\$\endgroup\$
  • \$\begingroup\$ Great points. Liked the use of the tuple to destructure the left half and the right half of the array. Thanks! \$\endgroup\$ – sc_ray Apr 1 '15 at 22:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.