Merge

[neverStopLearning]

I am having trouble figuring out how to display the number of moves the mergeSort algorithm completed in order to sort the array.

I believe the count variable is in the correct location, but the display part is eluding me.
Would it be appropriate to make this into a Class and make count a private data member? If so I am still a little confused on how to display the count.

// mergeSort.h
#pragma once

template<class ItemType>
void mergeSort(ItemType anArray[], int f, int l);

template<class ItemType>
void merge(ItemType theArray[], int first, int mid, int last);



#include "mergeSort.cpp"

// mergeSort.cpp

#include "mergeSort.h"
#include "sortSupport.h"
#ifndef MERGESORT_CPP
#define MERGESORT_CPP

/**
	Merges two sorted array segments theArray[first...mid] and theArray[mid+1...last] 
	into one sorted Array.

	@pre first <=mid <= last. The subarrays, theArray[first...mid] and theArray[mid+1...last]
		are sorted in ascending order.
	@post theArray[first...last] is sorted
	@param theArray[]
	@param the index of the first position in the first segment in the array (int first)
	@param the index of the last position in the first segment in the array (int mid), 
			(int mid + 1 is first position in the 2nd segment in the array)
	@param the index of the last position in the 2nd segment in thee array (int last)
*/
template<class ItemType>
void merge(ItemType theArray[], int first, int mid, int last)
{

	ItemType tempArray[MAX_SIZE]; // temp array

	int first1 = first;
	int last1 = mid;
	int first2 = mid + 1;
	int last2 = last;

	int index = first1;
	while ((first1 <= last1) && (first2 <= last2))
	{
		if (theArray[first1] <= theArray[first2])
		{
			tempArray[index] = theArray[first1];
			first1++;
		
		}
		else
		{
			tempArray[index] = theArray[first2];
			first2++;
			
		}
		index++;
		count++;
	}
	while (first1 <= last1)
	{
		tempArray[index] = theArray[first1];
		first1++;
		index++;
	}
	while (first2 <= last2)
	{
		tempArray[index] = theArray[first2];
		first2++;
		index++;
	}
	
	//Copy temp array back into original array
	for (index = first; index <= last; index++)
	{
		theArray[index] = tempArray[index];
	}
	//cout << "Merge had " << count << " moves" << endl;
}
template<class ItemType>
void mergeSort(ItemType anArray[], int first, int last)
{
	
	if (first < last)
	{
		int mid = first + (last-first) / 2;

		mergeSort(anArray, first, mid);
		
		mergeSort(anArray, mid + 1, last);
		
		merge(anArray, first, mid, last);
		
	}

} 
int getCount(){
	
	return count;
}
#endif 

// main

#include "sortSupport.h"
#include "bubbleSort.h"
#include "mergeSort.h"
#include <iostream>

using namespace std;

int main()
{
	// int count = 0;
	int ary[MAX_SIZE];
	int seed;
	cout << "The seed to use is: ";
	cin >> seed;
	makeArray<int>(ary, MAX_SIZE, seed);
	cout << "Bubble sort unsorted\n";
	printEnds<int>(ary, MAX_SIZE);
	bubbleSort<int>(ary, MAX_SIZE);
	cout << "Bubble sort sorted\n";
	printEnds<int>(ary, MAX_SIZE);
	cout << "The seed to use is: ";
	cin >> seed;
	cin.ignore();
	makeArray<int>(ary, MAX_SIZE, seed);
	cout << "Merge sort sorted\n";
	mergeSort<int>(ary, 0, MAX_SIZE-1);
	
	printEnds<int>(ary, MAX_SIZE);
	system("pause");
	return 0;
}

[coder777]

Change:

template<class ItemType>
int mergeSort(ItemType anArray[], int f, int l); // The result is the count

template<class ItemType>
int merge(ItemType theArray[], int first, int mid, int last); // The result is the count 

Within mergeSort(...) you simply add the [recursive] resulting counts.

[neverStopLearning]

I have tried out this solution and now the mergeSort does not sort the array nor does it output the number of moves.

// mergeSort.h
#pragma once

template<class ItemType>
int mergeSort(ItemType anArray[], int f, int l);

template<class ItemType>
int merge(ItemType theArray[], int first, int mid, int last);



#include "mergeSort.cpp" 

template<class ItemType>
int merge(ItemType theArray[], int first, int mid, int last)
{
        int count = 0;
	ItemType tempArray[MAX_SIZE]; // temp array

	int first1 = first;
	int last1 = mid;
	int first2 = mid + 1;
	int last2 = last;

	int index = first1;
	while ((first1 <= last1) && (first2 <= last2))
	{
		if (theArray[first1] <= theArray[first2])
		{
			tempArray[index] = theArray[first1];
			first1++;
		
		}
		else
		{
			tempArray[index] = theArray[first2];
			first2++;
			
		}
		index++;
		count++;
	}
	while (first1 <= last1)
	{
		tempArray[index] = theArray[first1];
		first1++;
		index++;
	}
	while (first2 <= last2)
	{
		tempArray[index] = theArray[first2];
		first2++;
		index++;
	}
	
	//Copy temp array back into original array
	for (index = first; index <= last; index++)
	{
		theArray[index] = tempArray[index];
	}
	return count;
}
template<class ItemType>
void mergeSort(ItemType anArray[], int first, int last)
{
	int count = 0;
	if (first < last)
	{
		int mid = first + (last-first) / 2;

		mergeSort(anArray, first, mid);
		count++;
		mergeSort(anArray, mid + 1, last);
		count++;
		merge(anArray, first, mid, last);
		
	}
         return count;
} 

// main

#include "sortSupport.h"
#include "bubbleSort.h"
#include "mergeSort.h"
#include <iostream>

using namespace std;

int main()
{
	// int count = 0;
	int ary[MAX_SIZE];
	int seed;
	cout << "The seed to use is: ";
	cin >> seed;
	makeArray<int>(ary, MAX_SIZE, seed);
	cout << "Bubble sort unsorted\n";
	printEnds<int>(ary, MAX_SIZE);
	bubbleSort<int>(ary, MAX_SIZE);
	cout << "Bubble sort sorted\n";
	printEnds<int>(ary, MAX_SIZE);
	cout << "The seed to use is: ";
	cin >> seed;
	cin.ignore();
	makeArray<int>(ary, MAX_SIZE, seed);
	cout << "Merge sort sorted\n";
	mergeSort<int>(ary, 0, MAX_SIZE-1);
	
	printEnds<int>(ary, MAX_SIZE);
	system("pause");
	return 0;
}

[neverStopLearning]

ahh I figured it out. Was unable to wrap my head around setting the recursive call to an int count variable.

Thank you for the help @coder777