The following code fragment tests the mergesort agent in the class. First, we set up the list for sorting.
{
int input[10] = {2,2,3,12,-1,45,17};
cout << "Instantiating List Qaitlin" << endl;
INT_SLLIST Qaitlin("intQa1");
cout << endl << "Building Qaitlin List" << endl;
Qaitlin.build_list(input,7);
cout << "Qaitlin has " << Qaitlin.get_number_elements() << " elements";
cout << endl;
cout << endl << "Qaitlin = " << endl << Qaitlin << endl;
cout << endl << "Insert element 10 after 3" << endl;
Qaitlin.insert_after(3,10);
cout << endl << "Qaitlin = " << Qaitlin;
cout << endl << "Insert element 20 after 2" << endl;
Qaitlin.insert_after(2,20);
cout << endl << "Qaitlin = " << Qaitlin;
cout << endl << "Insert element 30 before 17" << endl;
Qaitlin.insert_before(17,30);
cout << endl << "Qaitlin = " << Qaitlin;
which generates the output
Instantiating List Qaitlin In default SLLIST<intQa1> constructor. Exit default SLLIST<intQa1> constructor. Building Qaitlin List In SLLIST<intQa1> build_list. Exit SLLIST<intQa1> build_list. Qaitlin has 7 elements Qaitlin = 2-->2-->3-->12-->-1-->45-->17. Insert element 10 after 3 Entering the SLLIST insert_after. In SLLIST get_after_element_address. In SLLIST get_element_adress. Leaving the SLLIST insert_after. Qaitlin = 2-->2-->3-->10-->12-->-1-->45-->17. Insert element 20 after 2 Entering the SLLIST insert_after. In SLLIST get_after_element_address. search_key is at head of list, so after address is head->next. In SLLIST get_element_adress. Leaving the SLLIST insert_after. Qaitlin = 2-->20-->2-->3-->10-->12-->-1-->45-->17. Insert element 30 before 17 Entering the SLLIST insert_before. In SLLIST get_before_element_address. In SLLIST get_element_adress. Leaving the SLLIST insert_before. Qaitlin = 2-->20-->2-->3-->10-->12-->-1-->45-->30-->17.
Then we call the mergesort function, Qaitlin.mergesort().
cout << "Qaitlin has " << Qaitlin.get_number_elements() << " elements"; cout << endl << "Sort the list Qaitlin." << endl; Qaitlin.mergesort(); cout << endl << Qaitlin << endl; }
The output shows the sorted list and the destructor calls upon leaving scope.
Qaitlin has 10 elements Sort the list Qaitlin.
-1-->2-->2-->3-->10-->12-->17-->20-->30-->45.
Entering SLLIST<intQa1> destructor.
Removing SL_CELL -1
Removing SL_CELL 0
Removing SL_CELL 1
Removing SL_CELL 2
Removing SL_CELL 3
Removing SL_CELL 4
Removing SL_CELL 5
Removing SL_CELL 6
Removing SL_CELL 7
Removing SL_CELL 8
Leaving SLLIST destructor.
We will now temporarily add some additional diagnostic statements to the mergesort agents in the INT_SL_CELL class so that we can follow the mergesort details. Upon running the code fragment above again, the mergesort call now generates a lot more output!
Qaitlin = 2-->20-->2-->3-->10-->12-->-1-->45-->30-->17.
Qaitlin has 10 elements
Sort the list Qaitlin.
MergeSort of chain 2-->20-->2-->3-->10-->12-->-1-->45-->30-->17. = A
Call split(temp1) in mergesort:
Splitting chain 2-->20-->2-->3-->10-->12-->-1-->45-->30-->17.
Split temp1 getting temp2
return new temp2 and call split(temp2->next)
Splitting chain 2-->3-->10-->12-->-1-->45-->30-->17.
Split temp2->next
return new temp2 and call split(temp2->next)
Splitting chain 10-->12-->-1-->45-->30-->17. = temp2->next
return new temp2 and call split(temp2->next)
Splitting chain -1-->45-->30-->17. = temp2->next
return new temp2 and call split(temp2->next)
Splitting chain 30-->17. = temp2->next
return new temp2 and call split(temp2->next)
Splitting chain
temp 1 = 2-->2-->10-->-1-->30.
temp 2 = 20-->3-->12-->45-->17.
Split returns chain 20-->3-->12-->45-->17 <==== This is half of original
and is final new temp2
Call MergeSort(temp1) temp1 plays role of A in code
MergeSort of chain 2-->2-->10-->-1-->30. = new A
Splitting chain 2-->2-->10-->-1-->30. = split A to get temp2
Splitting chain 10-->-1-->30. = split temp2->next to get temp2
Splitting chain 30. = split temp2->next to get temp2
temp 1 = 2-->10-->30.
temp 2 = 2-->-1.
Split returns 2-->-1. = new temp2
Call MergeSort(temp1) temp1 plays role of A in code
MergeSort of chain 2-->10-->30. = new A
Splitting chain 2-->10-->30. = split A to get temp2
Splitting chain 30. = split temp2->next to get temp2
temp 1 = 2-->30.
temp 2 = 10.
Split returns 10. = new temp2
Call MergeSort(temp1) temp1 plays role of A in code
MergeSort of chain 2-->30. = new A
Splitting chain 2-->30. = Split A to get temp2
Splitting chain
temp 1 = 2.
temp 2 = 30.
Split returns 2 = new temp2
Call MergeSort(temp1) temp1 plays role of A in code
MergeSort of chain 1. = new A, no split needed,
returns temp1 = 2.
The original call to MergeSort for 2-->2-->10-->-1-->30.
has been resolved and the first argument of the
original call is now returned as 2.
We now back out of the recursion
using the temp1 at this point which is temp2 = 30.
MergeSort of chain 30.
This is the second part of the call
merge(mergesort(temp1),mergesort(temp2));
The mergesort(temp2) is thus mergesort(30.) which
returns 30.
We can now resolve the call merge(2.,30.);
Merging chains 2. and 30.
2 <= 30 so we set the next pointer for
the cell temp1 (which has value 2) to
temp1->next = merge(temp1->next,temp2) = merge(NULL.,30.).
Merging chains and 30.
This returns 30., so temp1->next = 30.
We have now resolved the call
mergesort(temp1) to 2.->30.
The next argument in the back up is
mergesort(temp2) = mergesort(10.)
MergeSort of chain 10.
Merging chains 2-->30. and 10.
Merging chains 30. and 10.
Merging chains 30. and NULL
MergeSort of chain 2-->-1.
Splitting chain 2-->-1.
Splitting chain
temp 1 = 2.
temp 2 = -1.
MergeSort of chain 2.
MergeSort of chain -1.
Merging chains 2. and -1.
Merging chains 2. and NULL
Merging chains 2-->10-->30. and -1-->2.
Merging chains 2-->10-->30. and 2.
Merging chains 10-->30. and 2.
Merging chains 10-->30. and NULL
We now have -1->2->2->10->30. the original temp1 from top
We now start to mergesort the list temp2
MergeSort of chain 20-->3-->12-->45-->17.
Splitting chain 20-->3-->12-->45-->17.
Splitting chain 12-->45-->17.
Splitting chain 17.
temp 1 = 20-->12-->17.
temp 2 = 3-->45.
MergeSort of chain 20-->12-->17.
Splitting chain 20-->12-->17.
Splitting chain 17.
temp 1 = 20-->17.
temp 2 = 12.
MergeSort of chain 20-->17.
Splitting chain 20-->17.
Splitting chain
temp 1 = 20.
temp 2 = 17.
MergeSort of chain 20.
MergeSort of chain 17.
Merging chains 20. and 17.
Merging chains 20. and NULL
MergeSort of chain 12.
Merging chains 17-->20. and 12.
Merging chains 17-->20. and NULL
MergeSort of chain 3-->45.
Splitting chain 3-->45.
Splitting chain
temp 1 = 3.
temp 2 = 45.
MergeSort of chain 3.
MergeSort of chain 45.
Merging chains 3. and 45.
Merging chains NULL and 45.
Merging chains 12-->17-->20. and 3-->45.
Merging chains 12-->17-->20. and 45.
Merging chains 17-->20. and 45.
Merging chains 20. and 45.
Merging chains and 45.
We now have sorted temp2 = 3-->12-->17-->20-->45.
We now merge the sorted chains temp1 and temp2
Merging chains -1-->2-->2-->10-->30. and 3-->12-->17-->20-->45.
Merging chains 2-->2-->10-->30. and 3-->12-->17-->20-->45.
Merging chains 2-->10-->30. and 3-->12-->17-->20-->45.
Merging chains 10-->30. and 3-->12-->17-->20-->45.
Merging chains 10-->30. and 12-->17-->20-->45.
Merging chains 30. and 12-->17-->20-->45.
Merging chains 30. and 17-->20-->45.
Merging chains 30. and 20-->45.
Merging chains 30. and 45.
Merging chains NULL and 45.
Giving the Sorted List =
-1-->2-->2-->3-->10-->12-->17-->20-->30-->45.