Template version of merge sort

[Leo78963]

Hi there,
How do you create a template version of the merge sort below?
Many thanks in advance.


#include <iostream>

using namespace std;

// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;

// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}

// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}

// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;
}


// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}

// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);

// Merge them to get sorted output.
Merge(a, low, high, mid);
}
}

int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;

int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}

MergeSort(arr, 0, n-1);

// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];

return 0;
}

[Repeater]

First up, fix this illegal C++:

int temp[high-low+1];

cin>>n;
int arr[n];

C++ does not allow variable length arrays like this.


Then, you're looking for something like this at the start of your functions.

it's up to you to identify values inside your functions that should be of type T.

template <class T>
void Merge(T *a, T low, T high, T mid) // Should ALL of these be template type?
{
	...

// A function to split array into two parts.
template <class T>
void MergeSort(T *a, T low, T high)  // Should ALL of these be template type?
{ ...