title: C++ Merge sort of linked list is not sorting the first two indices
body: <p>I am getting a bit lost trying to figure out how to recursively merge sort my linked list. I have tried following some guides but I'm getting a bit lost with all the pointers and recursion. It feels like the problem is with the merge function once the lists have a single node each.</p>
  
  <p>I have a <code>Node</code> class and a list class. I have left out other member functions to make it more readable. Here are the classes. Sorry some of the variable names aren't the best in the functions.</p>
  
  <pre><code>class Node {
    public:
      int val;
      Node *next;
  };
  
  class Linked_list {
    private:
      unsigned int length;
      Node *head;
      Node *tail;
    public:
      void sort_ascending();
      void merge_sort(Node **);
      void halve(Node *&amp;, Node *&amp;, Node *&amp;);
      Node* merge(Node *, Node *);
  };
  </code></pre>
  
  <p>I start with <code>sort_ascending()</code> which creates a <code>Node</code> pointer and sets it to the first node in the list and then calls <code>merge_sort</code> with the pointer as a parameter. </p>
  
  <pre><code>void Linked_list::sort_ascending() {
      Node *h = head-&gt;next;
      merge_sort(&amp;h);
  }
  </code></pre>
  
  <p><code>merge_sort</code> checks if the first two indices are <code>NULL</code>, returns if they are. Otherwise the linked list is halved.</p>
  
  <pre><code>void Linked_list::merge_sort(Node **h) {
      Node *t = *h;
      Node *a;
      Node *b;
      if ((t == NULL) || (t-&gt;next == NULL)) {
          return;
      }
      halve(t, a, b);
      merge_sort(&amp;a);
      merge_sort(&amp;b);
      *h = merge(a, b);
      return;
  }
  </code></pre>
  
  <p>Here is the function for splitting the list in halves. </p>
  
  <pre><code>void Linked_list::halve(Node *&amp;t, Node *&amp;a, Node *&amp;b) {
      Node *h1 = t;
      Node *h2 = t-&gt;next;
      while (h2 != NULL) {
          h2 = h2-&gt;next;
          if (h2 != NULL) {
              h1 = h1-&gt;next;
              h2 = h2-&gt;next;
          }
      }
      a = t;
      b = h1-&gt;next;
      h1-&gt;next = NULL;
  }
  </code></pre>
  
  <p>Finally the merge function.</p>
  
  <pre><code>Node *Linked_list::merge(Node *a, Node *b) {
      Node *h = NULL;
      if (a == NULL) {
          return b;
      }
      if (b == NULL) {
          return a;
      }
      if (a-&gt;val &lt;= b-&gt;val) {
          h = a;
          h-&gt;next = merge(a-&gt;next, b);
      } else {
          h = b;
          h-&gt;next = merge(a, b-&gt;next);
      }
      return h;
  }
  </code></pre>
  
  <p>When I run my program and enter/print a few values I get:</p>
  
  <pre><code>9 4 32 2 6
  </code></pre>
  
  <p>Then when I sort it the output becomes: </p>
  
  <pre><code>9 4 2 6 32
  </code></pre>