MCX2                                                                                                                 Math Department
Mr. Gary. Jaye                                                                                                    Danny Jaye, A.P.S.

1994 APCS AB Exam: Question 4

Consider sorting a linked list of integers. Linked lists are implemented
using the following definitions.

struct nodeType {
  long info;
  nodeType *next;
};

In this problem you will be asked to implement a merge sort. To sort
a list A using merge sort, the followiing algorithm is used.

1. Split the list A into two lists.
2. Recursively sort these two lists (using merge sort).
3. Merge the two (now-sorted) lists together

If the list to be sorted is A, an example of the approach is:

A--> 5--> 15--> 8--> 2--> 13--> 4--> 12--> NULL

1. Split list A into two lists,

A--> 5--> 15--> 8--> 2--> NULL
B--> 13--> 4--> 12--> NULL

2. Recursively sort these two lists,

A--> 2--> 5--> 8--> 15--> NULL
B--> 4--> 12--> 13--> NULL

3. and merge the two (now-sorted) lists together.

A--> 2--> 4--> 5--> 8--> 12--> 13--> 15--> NULL

Part A

Write function mergeSort whose protype is given below. In writing
mergeSort, you may call on split and merge whose specifications are
given below.

void split(nodeType *&A, nodeType *&B);
//post: The list represented by A into 2 lists A and B
//      whose lengths differ by no more than 1

void merge(nodeType *&A, nodeType *B);
//pre: A represents the sorted list of integers a1 < a2 < ... < aj, j >= 0
//     B represents the sorted list of integers b1 < b2 < ... < bk, k >= 0
//post: A represents the sorted list of integers c1 < c2 < ... cj+k,
//      each ai and bi appear exactly once as an element of A

Complete function mergeSort below.

Part B

Assume merge(A, B) executes in O(m) time, where m is the total number of
nodes in A and B. Further assume that function split is implemented as
shown below, __failing__ to meet the specification that the lists A and
B differ by no more than 1.

void split(nodeType *&A, nodetype *&B) {
   if ( A != NULL ) {
      B = A->next;
      A->next = NULL;
   }
}//*** split

Give the big-O expression for the execution time for mergeSort(A), where
A has K nodes. Briefly justify your answer.

Part C

Write the correct version of function split that meets the specification
that the two lists produced by split differ in length by no more than 1.

Complete function split below;

void split(nodeType *&A, nodeType *&B) {