/******************************************************

** Name: 

** Filename: MergeSort.cpp

** Project #: Data Structures And Other Objects Using C++ 2nd Edition
              (Micheal Main & Walter Savich)
              <Pg. 611-622>


** Project Description: Implement a MergeSort using
   a MergeSort function and a Merge function.

** Output: Sorted array of integers

** Input:  None 

** Algorithm:

******************************************************/
// Include files
#include <iostream>  // used for cin, cout
#include <conio.h>
#include <iomanip>
#include <ctime>
#include <cstdlib>
using namespace std;

// Global Type Declarations

// Function Prototypes
void instruct (void);
void pause ();    
void mergesort(int data[], size_t n);
void merge(int data[], size_t n1, size_t n2);
void display(int data[], size_t n);

//Global Variables - should not be used without good reason.

int main ()
{
	 // Declaration section
	 const size_t size = 6;
	 int num[size];
	 srand (time (0) );

	 // Executable section
	 instruct ();	
	 
	 for (int i = 0; i < size; i++)
             num[i] = rand() % 50;
	
         cout << "Unsorted Array" << endl;
         display(num,size);

         mergesort(num, size);

	 cout << "\n\nSorted Array" << endl;
	 display(num, size);

	 pause ();
	 return 0;
}

void mergesort(int data[], size_t n)
{
	size_t n1;
	size_t n2;

	if (n > 1)
	{
	  n1 = n / 2;
	  n2 = n - n1;

	  mergesort(data, n1);
	  mergesort((data + n1), n2);
      
	  merge(data, n1, n2);
	}
}

void merge(int data[], size_t n1, size_t n2)
{
	int *temp;
	size_t copied = 0;
	size_t copied1 = 0;
	size_t copied2 = 0;
	size_t i;

	temp = new int[n1 + n2];

	while ((copied1 < n1) && (copied2 < n2))
	{
		if(data[copied1] < (data + n1)[copied2])
		  temp[copied++] = data[copied1++];

		else
		  temp[copied++] = (data + n1)[copied2++];
	}
    
	while (copied1 < n1)
	      temp[copied++] = data[copied1++];
	while (copied2 < n2)
	      temp[copied++] = (data + n1)[copied2++];

	for (i = 0; i < n1 + n2; ++i)
	    data[i] = temp[i];
	delete [] temp;
    	
}
		   
void display(int data[], size_t n)
{
	int row = 0;

	for (int i = 0; i < n; i++)
	{ 
		cout << data[i] << "  ";
	
	row++ ;  
	if (row % 10 == 0 )
	{
		cout << "\n";
	}

	
	}
}

void instruct (void)
{
	  // Declaration section

	  // Executable section
}

void pause ()
{
    // Declaration section

    // Executable section
    cout << "\nPress any key to continue...";
    getch();
    cout << "\r";
    cout << "                            ";
    cout << "\r";
}


/*
Program Output

Unsorted Array
40  16  23  13  23  6

Sorted Array
6  13  16  23  23  40
Press any key to continue...

*/