title: Algorithm: Merge Sort with linked list missing items
body: <p>I am trying to sort my linked list with merge sort. The list is actually sorted but it is kind of missing first item(s).</p>
  
  <p>Merge sort functions:</p>
  
  <pre><code>public Node mergeSort(Node head) {
      if (head == null || head.next == null) {
          return head;
      }
  
      Node middle = middleElement(head);
      Node nextofMiddle = middle.next;
      middle.next = null;
      return merge(mergeSort(head), mergeSort(nextofMiddle));
  }
  
  public Node merge(Node left, Node right) {
  
      Node temp = new Node();
      Node newHead = temp;
      while (left != null &amp;&amp; right != null) {
          if (left.info &lt;= right.info) {
              temp.next = left;
              temp = left;
              left = temp.next;
          } else {
              temp.next = right;
              temp = right;
              right = temp.next;
          }
      }
      temp.next = (left == null) ? right : left;
      return newHead;
  }
  
  public Node middleElement(Node head) {
      if (head == null) {
          return head;
      }
      Node slow = head;
      Node fast = head;
      while (fast.next != null &amp;&amp; fast.next.next != null) {
          slow = slow.next;
          fast = fast.next.next;
      }
      return slow;
  }
  </code></pre>
  
  <p>So I printed the list to the screen using traverse:</p>
  
  <pre><code>    public static void main(String[] args) {
      MyLinkedList mll = new MyLinkedList();
  
      mll.insert(3);
      mll.insert(5);
      mll.insert(9);
      mll.insert(1);
      mll.insert(8);
      mll.insert(7);
      mll.insert(2);
  
  
  
      mll.mergeSort(mll.head);
      mll.traverse();
  
  }
  </code></pre>
  
  <p>I have result like this:
  <a href="https://i.stack.imgur.com/9VkIE.png" rel="nofollow noreferrer">1 and 2 missing!</a></p>
  
  <p>After checking, i noticed that the "tail" of the linked list value is still 2. I don't know why can someone help?. I'm really new to programming so sorry for any inconvenience. Thank you for reading!</p>