This article describes an implementation of the Mergesort Algorithm.
To make the implementation challenging, we will swap nodes instead of swapping content.
Mergesort implementation.
int mergesort( Node ** list ){ int listSize = 0; int i; Node * listPointer; Node * list1Pointer; Node * list2Pointer; if( !list ){ return -1; } if( !*list ){ return 0; } //divide list into two after counting size of original list for( listPointer = *list; listPointer; listPointer = listPointer->next ){ listSize++; } i = listSize / 2; for( listPointer = *list; i > 0; i-- ){ listPointer = listPointer->next; } list2Pointer = listPointer->next; listPointer->next = 0; list1Pointer = *list; //recursively mergesort both lists if( mergesort( &list1Pointer ) ){ return -3; } if( mergesort( &list2Pointer ) ){ return -3; } //need first node, take smaller of two if( list2Pointer ){ if( list1Pointer->content < list2Pointer->content ){ listPointer = list1Pointer; list1Pointer = list1Pointer->next; } else{ listPointer = list2Pointer; list2Pointer = list2Pointer->next; } *list = listPointer; //iterate through both lists and pick the next smallest for( ; list1Pointer || list2Pointer; ){ if( list1Pointer && list2Pointer ){ if( list1Pointer->content < list2Pointer->content ){ listPointer->next = list1Pointer; list1Pointer = list1Pointer->next; } else{ listPointer->next = list2Pointer; list2Pointer = list2Pointer->next; } } else if( list1Pointer ){ listPointer->next = list1Pointer; break; } else{ listPointer->next = list2Pointer; break; } listPointer = listPointer->next; } } else{ *list = list1Pointer; } return 0; }