// FILE: 94ab4.cpp    
// PURPOSE: 1994 AB Exam Question #4 
// COMPILATION INSTRUCTIONS: g++ 94ab4.cpp
/* ------------------------------------------------------------
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  
********************************************************************
**  Complete Part C __before__ Part A if you plan to run program  **
********************************************************************

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
-----------------------------------------------------------------*/
#include <iostream.h>
#include <iomanip.h>
#include <stdlib.h>
#include <string>

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

void split(nodeType *&A, nodeType *&B);
void merge(nodeType *&A, nodeType *B);
void insert(nodeType *&, long);
void print(nodeType *);
void loadAP_data(nodeType *&);
void cls(void);



//-------------------------------------
//          Part A  Code Part C first!!
//-------------------------------------
void mergeSort(nodeType *&A) {
  
}//*** mergeSort



//-------------------------------------
//           Part C
//-------------------------------------
void split(nodeType *&A, nodeType *&B) {
   B = NULL;
}//*** split



int main() { // --------------- main -------------------
  string title("1994 Exam AB: Question #4");
  nodeType *L, *L2;
  cls();
  cout << setw(40 + title.length()/2) << title.c_str() << "\n\n";

  loadAP_data(L);
  cout << "Before split(L):\n";
  print(L);
  split(L, L2);
  cout << "After split(L, L2):\n";
  print(L);  print(L2);


  loadAP_data(L);
  cout << "\nBefore mergeSort(L):\n";
  print(L);

  mergeSort(L);
  cout << "After mergeSort(L):\n";
  print(L);

  cout << "\n\n";
  cout << "Press <ENTER>: "; cin.ignore(80, '\n');
  return 0;
}//*** main


void loadAP_data(nodeType *&L) {
  L = NULL;
  insert(L, 12); insert(L, 4); insert(L, 13); insert(L, 2);
  insert(L, 8); insert(L, 15); insert(L, 5);
}//*** loadAP_data


void insert(nodeType *&L, long data) {
  nodeType *p = new nodeType;
  p->info = data;
  if ( L == NULL ) {
     L = p; L->next = NULL;
  }
  else {
    p->next = L; L = p;
  }
}//*** insert


void print(nodeType *L) {
  cout << "List--> ";
  if ( L != NULL ) {
    do {
      cout << L->info << "--> ";
      L = L->next;
    } while ( L != NULL );
  }
  cout << "NULL\n\n";
}//*** print


void cls(void) {
for (int k = 0; k < 55; k++)
  cout << endl;
}



void merge(nodeType *&A, nodeType *B) {
  nodeType *C, *head;
  if ( A == NULL ) {
    A = B; return;
  }
  else if ( B == NULL )
    return;
  if ( A->info > B->info ) { 
    head = B; B = B->next;
  }
  else {
    head = A; A = A->next;
  }
  C = head;
  while ( A != NULL && B != NULL ) {
    if ( A->info <= B->info ) {
      C->next = A; A = A->next;
    }
    else {
      C->next = B; B = B->next;
    }
    C = C->next;
  }//while
  if ( A != NULL ) { //*** append A's nodes
    C->next = A;
  }
  else {             //*** append B's nodes
    C->next = B;
  }
  A = head;          //*** make A the head
}//*** merge