This topic is 2921 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ok I'm working through some examples and exercises in my C++ book and I'm learning all about the ins and outs of linked lists, stacks, binary trees and such and I'm working on an exercise that requires me to sort a linked list. I've been doing research on sorting linked lists and have come to the conclusion that a merge sort is the best routine but the problem is that I'm having a hard time finding a good example of the algorithm to do so. I found one example of a merge sort on a linked list and tried to implement it into my class template linked list class but the list itself is not updating not to mention I'm having a hard time following their algorithm. So I guess what I'm asking is does anybody know of a good source for a linked list merge sort algorithm preferably something that's C++ oriented (if that makes sense).

##### Share on other sites
If you show us your code, we might be able to see the problems you're having. Link us to the example you're following too.

##### Share on other sites
Try to understand how and why the algorithm works. wikipedia has some good information http://en.wikipedia.org/wiki/Merge_sort (skip the more complicated parts at the end). The algorithm is the same independent of language so if you know your language good enough it shouldn't be too hard to translate pseudo code into C++. Focus on the meaning of the pseudo code statements and not on the syntax.

##### Share on other sites
Ok so first of all here is the example I'm using online [url="http://www.geeksforgeeks.org/archives/7740"]http://www.geeksforgeeks.org/archives/7740[/url] and I'm also looking at http://en.wikipedia.org/wiki/Merge_sort trying to figure it out. Ok here is the code to my linked list system including the merge sort routines.

Here is the node class:
 #ifndef LISTNODE_H #define LISTNODE_H template<typename NODETYPE> class List; template<typename NODETYPE> class ListNode { friend class List<NODETYPE>; // make list a friend public: ListNode(const NODETYPE &); // constructor NODETYPE getData() const; // return data in node private: NODETYPE data; // data ListNode<NODETYPE> *nextPtr; // next node in list }; // constructor template<typename NODETYPE> ListNode<NODETYPE>::ListNode( const NODETYPE &info ) : data(info), nextPtr(0) { // empty body } // return copy of data in node template<typename NODETYPE> NODETYPE ListNode<NODETYPE>::getData() const { return data; } #endif 

Here is the list class that contains a set of nodes
 #ifndef LIST_H #define LIST_H #include <iostream> #include "listnode.h" using namespace std; template<typename NODETYPE> class List { public: List(); // constructor ~List(); // destructor void insertAtFront( const NODETYPE & ); void insertAtBack( const NODETYPE & ); bool removeFromFront( NODETYPE & ); bool removeFromBack( NODETYPE & ); bool isEmpty() const; void print() const; void mergeSort(ListNode<NODETYPE> **headPtr); void listSplit(ListNode<NODETYPE>*, ListNode<NODETYPE>**, ListNode<NODETYPE>**); ListNode<NODETYPE> *sortedMerge(ListNode<NODETYPE>*, ListNode<NODETYPE>*); ListNode<NODETYPE> *getHead(); private: ListNode<NODETYPE> *firstPtr; // pointer to first node ListNode<NODETYPE> *lastPtr; // pointer to last node // utility function to allocate new node ListNode<NODETYPE> *getNewNode( const NODETYPE & ); // count of nodes in list(used for sort routine) int count; }; // default constructor template<typename NODETYPE> List<NODETYPE>::List() : firstPtr(0), lastPtr(0) { // empty body } // destructor template<typename NODETYPE> List<NODETYPE>::~List() { if (!isEmpty() ) // list is not empty { cout << "Destroying nodes...\n"; ListNode<NODETYPE> *currentPtr = firstPtr; ListNode<NODETYPE> *tempPtr; while (currentPtr != 0) // delete remaining nodes { tempPtr = currentPtr; cout << tempPtr->data << '\n'; currentPtr = currentPtr->nextPtr; delete tempPtr; } // end while } // end if count = 0; cout << "All nodes destroyed\n\n"; } template<typename NODETYPE> ListNode<NODETYPE> *List<NODETYPE>::getHead() { return firstPtr; } // insert node at front of list template<typename NODETYPE> void List<NODETYPE>::insertAtFront(const NODETYPE &value) { ListNode<NODETYPE> *newPtr = getNewNode( value ); // new node if ( isEmpty() ) // list is empty firstPtr = lastPtr = newPtr; // new list has only one node else // list is not empty { newPtr->nextPtr = firstPtr; // point new node to previous 1st node firstPtr = newPtr; // aim firstPtr at new node } count++; } // insert node at back of list template<typename NODETYPE> void List<NODETYPE>::insertAtBack(const NODETYPE &value) { ListNode<NODETYPE> *newPtr = getNewNode( value ); // new node if ( isEmpty() ) // list is empty firstPtr = lastPtr = newPtr; // new list has only one node else { lastPtr->nextPtr = newPtr; // update previous last node lastPtr = newPtr; // new last node } // end else count++; } // delete node from front of list template<typename NODETYPE> bool List<NODETYPE>::removeFromFront(NODETYPE &value) { if ( isEmpty() )// list is empty return false; else { ListNode<NODETYPE> *tempPtr = firstPtr; // hold tempPtr to delete if ( firstPtr == lastPtr ) firstPtr = lastPtr = 0; // no nodes remain after removal else firstPtr = firstPtr->nextPtr; // point to previous 2nd node value = tempPtr->data; // return data being removed delete tempPtr; // reclaim previous front node count--; return true; } } // delete node from back of list template<typename NODETYPE> bool List<NODETYPE>::removeFromBack(NODETYPE &value) { if ( isEmpty() ) // list is empty return false; else { ListNode<NODETYPE> *tempPtr = lastPtr; // hold tempPtr to delete if ( firstPtr == lastPtr ) // list has one element firstPtr = lastPtr = 0; // no nodes remain after removal else { ListNode<NODETYPE> *currentPtr = firstPtr; // locate second to last element while( currentPtr->nextPtr != lastPtr ) currentPtr = currentPtr->nextPtr; // move to next node lastPtr = currentPtr; // remove last node currentPtr->nextPtr = 0; // this is now the last node } value = tempPtr->data; // return value from old last node delete tempPtr; // reclaim former last node count--; return true; } } // sort the list of values template<typename NODETYPE> void List<NODETYPE>::mergeSort(ListNode<NODETYPE> **headPtr) { ListNode<NODETYPE> *head = *headPtr; ListNode<NODETYPE> *listA; ListNode<NODETYPE> *listB; // if list is empty or only has 1 entry just return if ((head == NULL) || (head->nextPtr == NULL)) return; listSplit(head, &listA, &listB); // recursive sort of lists mergeSort(&listA); mergeSort(&listB); // re point the head back to beginning of merged list *headPtr = sortedMerge(listA, listB); } template<typename NODETYPE> void List<NODETYPE>::listSplit(ListNode<NODETYPE> *head, ListNode<NODETYPE> **listA, ListNode<NODETYPE> **listB) { ListNode<NODETYPE> *fast; ListNode<NODETYPE> *slow; if (head == NULL || head->nextPtr == NULL) { *listA = head; listB = NULL; } else { slow = head; fast = head->nextPtr; // move fast 2 nodes ahead and slow 1 node ahead while(fast != NULL) { fast = fast->nextPtr; if (fast != NULL) { slow = slow->nextPtr; fast = fast->nextPtr; } } *listA = head; *listB = slow->nextPtr; slow->nextPtr = NULL; } } template<typename NODETYPE> ListNode<NODETYPE> *List<NODETYPE>::sortedMerge(ListNode<NODETYPE> *listA, ListNode<NODETYPE> *listB) { ListNode<NODETYPE> *result = NULL; if (listA == NULL) return listB; else if (listB == NULL) return listA; if (listA->data <= listB->data) { result = listA; result->nextPtr = sortedMerge(listA->nextPtr, listB); } else { result = listB; result->nextPtr = sortedMerge(listA, listB->nextPtr); } return result; } // is list empty? template<typename NODETYPE> bool List<NODETYPE>::isEmpty() const { return firstPtr == 0; } // return pointer to newly allocated node template<typename NODETYPE> ListNode<NODETYPE> *List<NODETYPE>::getNewNode(const NODETYPE &value) { return new ListNode<NODETYPE>(value); } // display contents of list template<typename NODETYPE> void List<NODETYPE>::print() const { if ( isEmpty() ) // list is empty { cout << "The list is empty\n\n"; return; } ListNode<NODETYPE> *currentPtr = firstPtr; cout << "The list is: "; while( currentPtr != 0 ) // get element data { cout << currentPtr->data << ' '; currentPtr = currentPtr->nextPtr; } cout << "\n\n"; } #endif 

Now I'm starting to think that I'm looking at this all the wrong way I think that I need to move my merge sort routines outside of the class and have them used on a list? Or I don't know I'm trying to make it so that you can have a list that has its own merge sort routine that updates the list itself. I know I'm close to figuring this out but just need a little help here.

Thanks again.

##### Share on other sites
It makes very little difference whether you use a member function or an external function whose first argument is a pointer to a list: They are essentially the same thing. I haven't read your code, but if you understand the algorithm, writing the code shouldn't be too hard. Little diagrams with boxes and arrows help a lot when trying to get all the pointers right.

##### Share on other sites
It looks like the sequence you get from mergeSort is correctly sorted. I think the problem is that you never update the firstPtr and lastPtr.

##### Share on other sites
Ok feel like an idiot lol the problem wasn't the sort routine it was the main program. I was passing a NULL pointer for the initial head pointer so the sort routine was kicking it back immediately without sorting it.

Thanks everybody for the help.

##### Share on other sites
Here is one more quick question related to merge sort that maybe somebody with more experience with it can explain to me. I noticed that when the list contains duplicate values that it has problems. I get results where it doesn't return all values and other times where some duplicates are missing and others are not. Any ideas as to why this is???

##### Share on other sites
It sounds like a bug to me. Try to come up with the smallest example you can where the algorithm fails, and then use a debugger to figure out what the program is doing exactly. Figure out why the code is doing something wrong and fix it.

##### Share on other sites
It looks right to me.

Do you update lastPtr after calling mergeSort?

I would remove the extra test at the top of listSplit. You already guaranteed that the head and next are not NULL just prior to calling it.
I would also write sortedMerge Iteratively rather than recursively. This can be an interesting learning exercise, and by the looks of what you're written already you could probably manage it.

[size="1"]Psst, see my website...

• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• 18
• 36
• 9
• 16
• 75