1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
|
// 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
| |