// Makefile

CXX=g++

main: main.o mergesort.o
	${CXX} -o main -std=c++11 main.o mergesort.o

clean:
	rm -f *.o main

\\ mergesort.h

class Mergesort{
	public:
		void printArray(const int a[], size_t size);
		void merge(int a[], size_t leftArraySize, size_t rightArraySize);
		void sort(int a[], size_t size);
};

\\ mergesort.cpp

#include<iostream>
#include "mergesort.h"

using namespace std;

void Mergesort::printArray(const int a[], size_t size) {
	cout << "Printing Array" << endl;
	for (int i = 0; i < size; i++) {
		cout << "a[" << i << "] = " << a[i] << endl;
	}
}


// algorithm from DS textbook
void Mergesort::merge(int a[], size_t leftArraySize, size_t rightArraySize) {

	// Note: we are assuming the left and right sub arrays are sorted

	int* tempArray;		// tempArray to hold sorted elements
	size_t copied = 0; 	// num elements copied to tempArray
	size_t leftCopied = 0;	// num elements copied from leftArray
	size_t rightCopied = 0;	// num elements copied from rightArray

	// create temp array
	tempArray = new int[leftArraySize + rightArraySize];
	// merge left and right arrays into temp in sorted order
	while ((leftCopied < leftArraySize) && (rightCopied < rightArraySize)) {
		if (a[leftCopied] < (a + leftArraySize)[rightCopied]) {
			tempArray[copied++] = a[leftCopied++];
		} else {
			tempArray[copied++] = (a + leftArraySize)[rightCopied++];
		}
		printArray(tempArray, leftArraySize + rightArraySize);
	}

	// copy remaining elements from left/right sub arrays into tempArray

	// if elements in leftArray still exist, then ...
	while (leftCopied < leftArraySize) {
		tempArray[copied++] = a[leftCopied++];
		printArray(tempArray, leftArraySize + rightArraySize);
	}


	// if elements in rightArray still exist, then ...
	while (rightCopied < rightArraySize) {
		tempArray[copied++] = (a + leftArraySize)[rightCopied++];
		printArray(tempArray, leftArraySize + rightArraySize);
	}

	// Replace the sorted values into the original array
	for (int i = 0; i < leftArraySize + rightArraySize; i++) {
		a[i] = tempArray[i];
	}

	// free up memory
	delete [] tempArray;
}


void Mergesort::sort(int a[], size_t size) {
	size_t leftArraySize;
	size_t rightArraySize;

	if (size > 1) {
		leftArraySize = size / 2;
		rightArraySize = size - leftArraySize;

		cout << endl << "Divide into sizes: " << leftArraySize << " and " << rightArraySize << endl;

		// call mergesort on left array
		cout << endl << "Sort left subarray:" << endl;
		printArray(a, leftArraySize);
		sort(a, leftArraySize); 
		
		// call mergesort on right array
		cout << endl << "Sort right subarray:" << endl;
		printArray((a + leftArraySize), rightArraySize);
		sort((a + leftArraySize), rightArraySize);

		cout << endl << "Merge the subarrays:" << endl;
		// left and right sorted arrays together
		merge(a, leftArraySize, rightArraySize);
	}
}

// main.cpp
#include <iostream>
#include "mergesort.h"

using namespace std;


int main() {
	int a[] = {0,1,2,3,4,5,6,7,8,9};
	int b[] = {9,8,7,6,5,4,3,2,1,0};
	int c[] = {0,9,1,8,2,7,3,6,4,5};
	int d[] = {5,4,6,3,7,2,8,1,9,0};

	Mergesort s;
	s.printArray(a, 10);
	s.sort(a, 10);
}

// Makefile
add quicksort.o to dependencies

// quicksort.h

class Quicksort{
	public:
		void printArray(const int a[], size_t size);
		void partition(int a[], size_t size, size_t& pivotIndex);
		void sort(int a[], size_t size);
};

// quicksort.cpp

#include<iostream>
#include "quicksort.h"

using namespace std;

void Quicksort::printArray(const int a[], size_t size) {
	cout << "Printing Array" << endl;
	for (int i = 0; i < size; i++) {
		cout << "a[" << i << "] = " << a[i] << endl;
	}
}

void Quicksort::partition(int a[], size_t size, size_t& pivotIndex) {
	int pivot = a[0];		 // choose 1st value for pivot
	size_t left = 1;		 // index just right of pivot
	size_t right = size - 1; // last item in array
	int temp;
	cout << endl <<"Chose a pivot: " << pivot << endl;
	printArray(a, size);
	while (left <= right) {
		// increment left if <= pivot
		while (left < size && a[left] <= pivot) {
			left++;
		}

		// decrement right if > pivot
		while (a[right] > pivot) {
			right--;
		}

		// swap left and right if left < right
		if (left < right) {
			cout << "Swapping: " << a[left] << " with " << a[right] << endl;
			temp = a[left];
			a[left] = a[right];
			a[right] = temp;
			printArray(a, size);
		}
	}
	cout << "Swapping pivot: " << a[0] << " with " << a[right] << endl;
	// swap pivot with a[right]
	pivotIndex = right;
	temp = a[0];
	a[0] = a[pivotIndex];
	a[pivotIndex] = temp;
	printArray(a, size);
}

void Quicksort::sort(int a[], size_t size) {
	size_t pivotIndex;		// index of pivot
	size_t leftSize;		// num elements left of pivot
	size_t rightSize;		// num elements right of pivot
	
	

	if (size > 1) {
		// partition a[] based on pivotIndex
		partition(a, size, pivotIndex);

		// Compute the sizes of left and right sub arrays
		leftSize = pivotIndex;
		rightSize = size - leftSize - 1;

		// recursive call sorting the left array
		sort(a, leftSize);

		// recursive call sorting the right array
		sort((a + pivotIndex + 1), rightSize);
	}
}

// add to main.cpp
#include "quicksort.h"