Node* sort (Node* beg)
{
  if(beg==tail || beg->next==tail) return beg;
  Node* a = beg; Node* b = beg->next;
  while(b!=tail && b->next != tail)
  {
    a = a->next; b = b->next->next;
  }
  b = a->next;  //the beginning of right part
  a->next = tail; //the end of left part
  return merge(sort(beg), sort(b));
}

Node* LinkedList<T>::merge(Node* a, Node* b)
{
 Node dummy = Node();
 Node* head = &dummy;
 // temp是正在合并的表的节点
 Node* temp = head;
 while(a!=tail && b!=tail) //逐个比较链表a和链表b的每个元素
 {
  if(a->data <= b->data)
  {
   // 如果a比b小, 那么当前结点的后继就是a
   temp->next = a;
   // 把当前节点移向后继
   temp = a;
   // a后移
   a = a->next;
  }
  else 
  {
   temp->next = b;
   temp = b; 
   b = b->next;
  }
  // 如果原表a已经排完,那么新表后面就放b的剩余元素
  // 否则仍然以a为标准和b进行比较
  temp->next = (a==tail) ? b : a;
 }
 return head->next;
}