static list mergeSortX( list sortMe )
{
	// Declare variables
	list left, right, result;
	int middle;
	double contents[2];
	double temp[2];
 
	printf("In mergeSortX with length %d\n", sortMe.count());
 
	// Return if the length is one or less
	if ( sortMe.count() <= 1 )
	{
		printf("returning = ");
		for ( int i = 0; i < sortMe.count(); i++ )
		{
			sortMe.access( i, temp );
			printf( "(%f, %f), ", temp[0], temp[1] );
		}
		printf("\n");
 
		printf("Sorted by length, returning...\n");
		return sortMe;
	}
 
	// Find the middle index of the list
	middle = sortMe.count() / 2;
	printf("middle = %d\n", middle);
 
	// Take elements 0 to middle and put them in left
	for( int i = 0; i < middle; i++ )
	{
		sortMe.access( i, contents );
		left.append( contents[0], contents[1] );
	}
 
	printf("left = ");
	for ( int i = 0; i < left.count(); i++ )
	{
		left.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");
 
 
	// Take elements middle to end and put them in right
	for( int j = middle; j < sortMe.count(); j++ )
	{
		sortMe.access( j, contents );
		right.append( contents[0], contents[1] );
	}
 
	printf("right = ");
	for ( int i = 0; i < right.count(); i++ )
	{
		right.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");
 
 
	// Sort the left and right lists recursively
	left = mergeSortX( left );
	printf("Sorted left = ");
	for ( int i = 0; i < left.count(); i++ )
	{
		left.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");
	right = mergeSortX( right );
 
	// Merge the result into one list
	printf("Merging lists...\n");
	result = mergeX( left, right );
 
	printf("result = ");
	for ( int i = 0; i < result.count(); i++ )
	{
		result.access( i, temp );
		printf( "(%f, %f), ", temp[0], temp[1] );
	}
	printf("\n");
 
	printf("Leaving mergeSortX\n");
 
	return result;
}
 
static list mergeX( list left, list right )
{
	// Declare variables
	list result;
	double firstLeft[2];
	double firstRight[2];
 
	// Merge the lists, maintaining order
	while ( ( left.count() > 0 ) and ( right.count() > 0 ) )
	{
		left.access( 0, firstLeft );
		right.access( 0, firstRight );
        	if ( firstLeft[0] <= firstRight[0] )
		{
			// Append the first element of left to the result and remove from left
			result.append( firstLeft[0], firstLeft[1] );
            		left.del( firstLeft[0], firstLeft[1] );
		}
        	else
        	{
			// Append the first element of right to the result and remove from right
			result.append( firstLeft[0], firstLeft[1] );
            		right.del( firstLeft[0], firstLeft[1] );
		}
	}
 
    	while ( left.count() > 0 ) 
	{
		left.access( 0, firstLeft );
		result.append( firstRight[0], firstRight[1] );
        	left.del( firstRight[0], firstRight[1] );
	}
 
    	while ( right.count() > 0 ) 
	{
		right.access( 0, firstRight );
		result.append( firstRight[0], firstRight[1] );
        	right.del( firstRight[0], firstRight[1] );
	}
 
    	return result;
 
}

class list
{
     private:
 
         struct node
         {
            double xData;
			double yData;
            node *link;
         }*p;
 
   public:
 
         list();
         void append( double x, double y );
         void del( double x, double y );
		 void access( int index, double contents[] );
         int count();
         ~list();
};
 
list::list()
{
     p=NULL;
}
 
void list::append( double x, double y )
{
   node *q,*t;
 
   if( p == NULL )
   {
      p = new node;
      p->xData = x;
	  p->yData = y;
      p->link = NULL;
   }
   else
   {
      q = p;
      while( q->link != NULL )
	  {
		  q = q->link;
	  }
 
      t = new node;
      t->xData = x;
	  t->yData = y;
      t->link = NULL;
      q->link = t;
   }
}
 
void list::del( double x, double y )
{
   node *q,*r;
   q = p;
 
   if(( q->xData == x ) && ( q->yData == y ))
   {
      p = q->link;
      delete q;
      return;
   }
 
   r = q;
   while( q!=NULL )
   {
      if(( q->xData == x ) && ( q->yData == y ))
      {
         r->link = q->link;
         delete q;
         return;
      }
 
      r = q;
      q = q->link;
   }
   printf("Element (%f, %f) not Found.\n", x, y);
}
 
void list::access( int index, double contents[])
{
	node *q;
    int c=0;
    for( q=p ; c<index ; c++ )
	{
        q = q->link;
	}
 
	contents[0] = q->xData;
	contents[1] = q->yData;
}
 
int list::count()
{
   node *q;
   int c=0;
   for( q=p ; q != NULL ; q = q->link )
        c++;
 
   return c;
}
 
list::~list()
{
   node *q;
   if( p == NULL )
        return;
 
   while( p != NULL )
   {
        q = p->link;
      delete p;
      p = q;
   }
}

doX = 1
List before = (-5.617623, -2.034482), (-5.506881, -2.153052), (-5.377584, -2.276156), (-5.249851, -2.403839), (-5.120810, -2.536295), (-4.969870, -2.675439), (-4.833482, -2.818779), (-5.732594, -1.919852), (-5.851091, -1.809288), (-5.956030, -1.701978), (-6.108007, -1.492484), 
In mergeSortX with length 11
middle = 5
left = (-5.617623, -2.034482), (-5.506881, -2.153052), (-5.377584, -2.276156), (-5.249851, -2.403839), (-5.120810, -2.536295), 
right = (-4.969870, -2.675439), (-4.833482, -2.818779), (-5.732594, -1.919852), (-5.851091, -1.809288), (-5.956030, -1.701978), (-6.108007, -1.492484), 
In mergeSortX with length 5
middle = 2
left = (-5.617623, -2.034482), (-5.506881, -2.153052), 
right = (-5.377584, -2.276156), (-5.249851, -2.403839), (-5.120810, -2.536295), 
In mergeSortX with length 2
middle = 1
left = (-5.617623, -2.034482), 
right = (-5.506881, -2.153052), 
In mergeSortX with length 1
returning = (-5.617623, -2.034482), 
Sorted by length, returning...