You are given a function mergeList() within the unorderedLinkedList header file to merge two sorted sublists. Provide the correct code implementations for the given blank code spaces. The final part after these implementations would be to implement a recursive merge sort function which utilizes both of these functions divideList() and mergeList(). The last function implementation would be for mergeSort(). mergeSort() function has to be a public member function of the unorderedLinkedList. Functions of divideList(), mereList() and recMergeSort() will be used to implement our mergeSort() function. We should write the missing codes where it says "COMMENT"

template nodeType* unorderedLinkedList::mergeList(nodeType* first1,nodeType* first2)

{ nodeType *lastSmall; //pointer to the last node of

//the merged list

nodeType *newHead; //pointer to the merged list

if (first1 == NULL) //the first sublist is empty

return first2;

else if (first2 == NULL) //the second sublist is empty

return first1;

else

{ if (/* Compare the first nodes here*/ ) COMMENT

{ /* add the code snippet in order to declare the newHead, first1 node and

lastSmall node into newhead*/COMMENT } else

{ newHead = first2;

first2 = first2->link;

lastSmall = newHead; }

while (first1 != NULL && first2 != NULL)

{ if (first1->info < first2->info){

lastSmall->link = first1;

lastSmall = lastSmall->link;

first1 = first1->link; }

else{

lastSmall->link = first2;

lastSmall = lastSmall->link;

first2 = first2->link;

}

} //end while

if (first1 == NULL) //first sublist is exhausted first

lastSmall->link = first2;

else //second sublist is exhausted first

lastSmall->link = first1;

return newHead; }

}//end mergeList

template

void unorderedLinkedList::recMergeSort(nodeType* &head)

{

nodeType *otherHead;

if (head != NULL) //if the list is not empty

if (head->link != NULL)

{ /* If the list has more than one node, divide the list by the head and the other head, after division is complete, you will call the code recursively in order to implement recMergeSort over heads lastly, initialize the hed by calling the mergeList() function */COMMENT }

} //end recMergeSort

template

void unorderedLinkedList::mergeSort() {

recMergeSort(first);

if (first == NULL)

last = NULL;

else

{ last = first;

while (last->link != NULL)

last = last->link; }

} //end mergeSort