#include<iostream.h>

#define null 0
struct numList
{
	int num;
	struct numList *next;
};

numList *natureSort( numList * );
numList *p3, *p4;

void main()
{
	int n = 0;
	numList * head;
	numList *p1, *p2;

	p1 = new numList;
	p2 = new numList;
    p3 = new numList;
	p4 = new numList;

	cout << "請輸入要排序的序列，以-1結束" << endl;

	cin >> p1->num;
	head = null;
	while( p1->num != -1 )
	{
		n++;
		if( n == 1)
			head = p1;
		else
			p2 -> next = p1;
		p2 = p1;
		p1 = new numList;
		cin >> p1 -> num;
	}
	p2 -> next = null;

	cout << "The original list is:" << endl;
	p1 = head;
	while( p1 != null)
	{
		cout << p1 -> num;
		p1 = p1 -> next;
		if( p1 != null)
			cout << "->";
	}
	cout << endl;

  p1 = natureSort( head );

  cout << "The sorted list is:" << endl;
  while( p1 != null )
  {
	  cout << p1 -> num;
	  p1 = p1 -> next;
	  if( p1 != null )
		  cout << "->";
  }
  cout << endl;

  delete p1;
  delete p2;
  delete p3;
  delete p4;

  return ;
}

numList * natureSort( numList * head)
{
  numList * first,* mid,* last;
  numList * sortedHead=head;
  numList * stop=sortedHead;
  numList * p=sortedHead;
  numList * first1,* first2;
  numList * head2;
  head2=null;

  while(true)
  {  
	  if(stop->next==null)
		  break;

	  while(stop->next->num>=stop->num)
	  {    
		   stop=stop->next;
	       if(stop->next==null)
                  break;
	  }

	  if(stop->next==null)
             break;

   

     int n=0;   
     while(p!=null)
	 { 
		first=p;
         
		if(p->next!=null)
	        while(p->next->num>=p->num&&p->next!=null)
			{     p=p->next;
		          if(p->next==null)
				      break;
			}  
	
		mid=p;
		if(p->next==null)
		{  
			last=p;
		}
		else
		{	p=p->next;
            if(p->next!=null)       
		          while(p->next->num>=p->num)
				  {
		              	p=p->next;
						if(p->next==null)
							break;
				  }
	    	last=p;
		}
		 
	 first1=first;
	 first2=mid->next ;
	 if(mid->next!=null)
	 {  
		 while(first1!=mid->next&&first2!=last->next)
		 { 
	         if(first1->num<=first2->num)
			 {   p3->num=first1->num;
	              first1=first1->next;
	               n++;
                if(n==1)
		           head2=p3;
	           else
	               p4->next=p3;
	           p4=p3;
	               p3=new numList;
			 }
          else
		  {     p3->num=first2->num;
	            first2=first2->next;
	            n++;
    	       if(n==1)
                  head2=p3;
	          else
 	            p4->next=p3;
	          p4=p3;
     	      p3=new numList;
		  }
		 }//end while
	 }//end if

    if(first1==mid->next)
       while(first2!=last->next)
	   {       p3->num=first2->num;
			   first2=first2->next;
	           n++;
               if(n==1)
		              head2=p3;
	            else
 	                  p4->next=p3;
	            p4=p3;
             	p3=new numList;
	   }
    else
        while(first1!=mid->next)
		{         p3->num=first1->num;
	              first1=first1->next; 
		          n++;
                  if(n==1)
		               head2=p3;
	                          
                 else
 	                  p4->next=p3;
	             p4=p3;
                 p3=new numList;
		 }

      p=p->next;
	 }
     
      p4->next=null;
	  sortedHead=head2;
	  head2=null;
	  p=sortedHead;
	  stop=sortedHead;

  }//end while(true)

  return sortedHead;

}