Below is a merge sort function provided by my instructor, my task is to create a program that asks the user to input numbers in random and choose which type of sorting algorithm he wants to use to be able to sort the numbers, I managed to finish quick sort and heap sort and I'm almost finished. But when I came across this merge sort function, there was this included parameter called "temp" that I don't understand, I tried to explore some pages on the internet but all of them are confusing... Can someone help me? I also included my program.

``````    void mergeSort(int numbers[], int temp[], int array_size)

{
m_sort(numbers, temp, 0, array_size - 1);

}

void m_sort(int numbers[], int temp[], int left, int right)

{
int mid;

if (right > left)

{

mid = (right + left) / 2;

m_sort(numbers, temp, left, mid);

m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);

}

}

void merge(int numbers[], int temp[], int left, int mid, int right)

{

int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;

tmp_pos = left;

num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))

{

if (numbers[left] <= numbers[mid])

{

temp[tmp_pos] = numbers[left];

tmp_pos = tmp_pos + 1;

left = left +1;

}

else

{

temp[tmp_pos] = numbers[mid];

tmp_pos = tmp_pos + 1;

mid = mid + 1;

}

}

while (left <= left_end)

{

temp[tmp_pos] = numbers[left];

left = left + 1;

tmp_pos = tmp_pos + 1;

}

while (mid <= right)

{

temp[tmp_pos] = numbers[mid];

mid = mid + 1;

tmp_pos = tmp_pos + 1;

}

for (i = 0; i <= num_elements; i++)

{

numbers[right] = temp[right];

right = right - 1;

}

}
``````

Here is my program:

``````        #include <iostream>
using namespace std;

void mergeSort(int numbers[], int temp[], int array_size);
void merge(int numbers[], int temp[], int left, int mid, int right);
void heapSort(int numbers[], int array_size);
void siftDown(int numbers[], int root, int bottom);
void quickSort(int numbers[], int array_size);
void q_sort(int numbers[], int left, int right);

int main()
{

int num, ch, i;
int arr[999] = {};

cout << "Enter number of nodes: ";
cin >> num;

for(i=0; i<num; i++)
{
cout << "Enter node: ";
cin >> arr[i];
}

cout << "\nHere are the unsorted nodes: ";
for(int i=0; i<num; i++)
{
cout <<""<<arr[i]<<" ";
}

choice:
cout << "\n\nChoices are:";
cout << "\n[1] Merge Sort"
<< "\n[2] Heap Sort"
<< "\n[3] Quick Sort"
<< "\n[4] Exit"
<< "\nEnter choice: ";

cin >> ch;

switch(ch)
{
case 1:
cout << "\nMerge" <<endl;
mergeSort(arr, num);

for(i=0; i<num; i++)
{
cout << ""<<arr[i]<<" ";
}
break;

case 2:
cout << "\nHeap Sort" <<endl;
heapSort(arr, num);

for(i=0; i<num; i++)
{
cout << ""<<arr[i]<<" ";
}
break;

case 3:
cout << "\nQuick Sort" <<endl;
quickSort(arr, num);

for(i=0; i<num; i++)
{
cout << ""<<arr[i]<<" ";
}
break;

case 4:
exit(1);
break;

default:
cout << "\nInvalid entry, try again";
goto choice;
break;
}

system("pause>null");
return 0;
}

void mergeSort(int numbers[], int temp[], int array_size)

{
m_sort(numbers, temp, 0, array_size - 1);

}

void m_sort(int numbers[], int temp[], int left, int right)

{
int mid;

if (right > left)

{

mid = (right + left) / 2;

m_sort(numbers, temp, left, mid);

m_sort(numbers, temp, mid+1, right);

merge(numbers, temp, left, mid+1, right);

}

}

void merge(int numbers[], int temp[], int left, int mid, int right)

{

int i, left_end, num_elements, tmp_pos;

left_end = mid - 1;

tmp_pos = left;

num_elements = right - left + 1;

while ((left <= left_end) && (mid <= right))

{

if (numbers[left] <= numbers[mid])

{

temp[tmp_pos] = numbers[left];

tmp_pos = tmp_pos + 1;

left = left +1;

}

else

{

temp[tmp_pos] = numbers[mid];

tmp_pos = tmp_pos + 1;

mid = mid + 1;

}

}

while (left <= left_end)

{

temp[tmp_pos] = numbers[left];

left = left + 1;

tmp_pos = tmp_pos + 1;

}

while (mid <= right)

{

temp[tmp_pos] = numbers[mid];

mid = mid + 1;

tmp_pos = tmp_pos + 1;

}

for (i = 0; i <= num_elements; i++)

{

numbers[right] = temp[right];

right = right - 1;

}

}

void heapSort(int numbers[], int array_size)
{
int i, temp;

for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);

for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}

void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;

done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;

if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}

void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}

void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;

l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
``````

## All 5 Replies

temp provides temporary space in which to perform the sort and should be the same size as the original array. While doing the sort the `merge` function uses the temp array to store the sorted list until is has complete the merge operation when it copies the sorted list back into the number array.

Using additional temporary storage in this manor is a common implementation of merge sort and would only be a problem where the size of the data set to be merged is beginning to get close to a small fraction of the available storage for the machine.

Thanks, so that means I'm going to pass the array size to temp right?

This means you have to create a second array of the same size as the one to be sorted, and pass that second array as the "temp" parameter to the merge sort function.

For Simple merge sort program refer java examples from http://www.tutorialdata.com its really helpful for understanding merge sort in simple programmimg.

Thank you so much guys, it's now working!!! :)

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, learning, and sharing knowledge.