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);
}
