void merge(ptr& a, ptr mid, ptr& b) {
  if (a!=NULL && mid!= NULL & b!=NULL) {
    ptr t1= a;  // Temporary pointers to the first half of the list
    ptr p1= a;  // When the loop gets going, p1 will always be the predecessor of t1.
                // We can't so that to begin with so we have a special case below.
  
    ptr p2= mid;  // Temporary pointers to the second half of the list
    ptr t2= mid->next; // When the loop gets going, p2 will always be the predecessor of t2.
    
    ptr end= b->next; // save where the end is
    // Remove items from the second half of the list and insert in the first half;
    // Invariant: (a upto previous node of t1) + sorted {(t1 up to mid) + (t2 up to mid)}
    //             is the sort of the original list segment.  
     while (t1!=mid->next && t2!=end) { // while there are still items to merge...
       if (t1->item > t2->item) { // test for merge; if t2 is in the wrong position ...
         ptr tt= t2;                // ...save t2 in tt...
         p2->next= t2->next;        // ... by-pass t2...
         tt->next= t1;              // ...  insert tt (the old t2) infront of t1
         if (p1 == t1) {p1= tt; a= tt; t2= p2-> next; // special case if p1 and t1 are the same         
         }
         else {
           p1->next= tt;           // otherwise finish the insert
           p1= tt;                 // establish the invariant for t1.
           t2= p2-> next;
         }
       }       
       else {
         p1= t1;       // establish invariant for t2
         t1= t1->next;
       }     
     } 
     if (t2==end) {b=p2;} // establish invariant for the last half
  }
}



 
// Note that this can be made to have O(1) space by moving the tt declaration outside the loop.