Merge Sort

[preetii90]

I am trying to use merge sort to sort a randomly arranged linked list. However, its not working properly. The code seems to compile but the sorting is not done correctly. Would someone be able to find out why...thanks.

ProductList::pdt* ProductList::merge(pdt* a, pdt* b)
{
	pdt	*ptmp;
	pdt	*sortedlist;
	
	//the current min value is the first value of the list
	double value=a->_price;
	
	//both nodes point to the same place, the begining of the list. 
	//I will not touch sortedlist, so that in the end I can simply
	//send the result of ptmp and a operations. sortedlist will always
	//point to the begining of the list which will be sorted as the 
	//program starts flowing
	ptmp = a;	
	sortedlist=a;
	
	
	//process of joining both lists, into a single list begining at a
	while(ptmp->_next!=NULL)
	{
		ptmp=ptmp->_next;
	}
	ptmp->_next=b;
	
	//'a' can now be treated like an array as it is a continous
	//linked list that needs to be sorted. 'a' is the head of the linked
	//list. It is very easy now.
	
	//mergesort algorithm, slightly adapted from the book. It does the same
	//thing, but instead of using arrays, it uses linked lists.
	while(a->_next!=NULL)
	{
		value=a->_price;
		ptmp=a;
		while(ptmp->_next!=NULL)
		{
			ptmp=ptmp->_next;
			
			if (ptmp->_price<value)
			{
				value=ptmp->_price;
				ptmp->_price=a->_price;
				a->_price=value;
			}
		}
		a=a->_next;
		
	}
	
	
	return(sortedlist);
}


// Takes a pointer to the first node of a linked list and breaks the 
// list into two pieces, then recursively sorts each piece and merges the 
// two sorted sublists using the merge function.
ProductList::pdt* ProductList::mergeSort(pdt *pHead)
{
	
	pdt	*tmpNode;
	pdt	*pNode;
	
	//if there is an object
	if (pHead->_next!=NULL)
	{
		
		int i=0,size=0;
		
		//calculating the size of the linkedlist
		for(tmpNode=pHead;(tmpNode->_next)!=NULL;tmpNode=tmpNode->_next)
			size++;
		
		//puts tmpNode back in the origin of the linked list
		tmpNode=pHead;
		
		//beginning to split the list in two... first half will be with
		//pHead
		for(i=0;i<size/2;i++)
			tmpNode=tmpNode->_next;
		
		//second half will be with pNode
		pNode=tmpNode->_next;
		
		//breaking the chain here... so we can have two lists
		tmpNode->_next=NULL;
		
		//merges the lists after recusively mergesorting them
		pHead=mergeSort(pHead);
		
		pNode = mergeSort(pNode);
		
		pHead=merge(pHead,pNode);
		
	}
	
	return(pHead);
	
}

[jsmith]

A good way to debug algorithmic problems is to sprinkle the code with a lot of print statements
that say what is happening. Since you know what _should_ be happening, you'll be able to
see where your algorithm is going wrong by what it is outputting.

(Debugging skills are equally important to coding skills.)

[moorecm]

Also start with a very small list such that the output is not overwhelming. I often work out expected results on paper first.

[preetii90]

the problem actually occurs at this line: while(a->_next!=NULL)

i tried to work out the code on paper and i realized its not sorting properly for example with the sample input of: 7,11,5,21.

with my code, it sorts up to 7,5,11,21.

however, it needs to sort one more time to get 5,7,11,21.

does anyone know how to solve this?
thankss!

[jsmith]

I suggest looking up the mergesort algorithm on wikipedia.

Did you add the prints?

[preetii90]

Actually, when i tried this code with integer variables rather than using double variables, it works perfectly. If that's the case, what should i do for it to work with decimals also.
thanks