Hi everybody,
I'm trying to figure out how much memory was used for merge sort algorithm. I believe it is just one or two expressions, but can't come up with them by my own.
public void mergeSort (T[] data, int min, int max)
{
T[] temp;
int index1, left, right;
/** return on list of length one */
if (min==max)
return;
/** find the length and the midpoint of the list */
int size = max - min + 1; // size of the array
int pivot = (min + max) / 2; // middle point
temp = (T[])(new Comparable[size]);
mergeSort(data, min, pivot); // sort left half of list
mergeSort(data, pivot + 1, max); // sort right half of list
/** copy sorted data into workspace */
for (index1 = 0; index1 < size; index1++)
temp[index1] = data[min + index1];
/** merge the two sorted lists */
left = 0;
right = pivot - min + 1;
for (index1 = 0; index1 < size; index1++)
{
if (right <= max - min)
if (left <= pivot - min)
if (temp[left].compareTo(temp[right]) > 0)
data[index1 + min] = temp[right++];
else
data[index1 + min] = temp[left++];
else
data[index1 + min] = temp[right++];
else
data[index1 + min] = temp[left++];
}
}