template <class Type>
void merge(Type arry[], int s1, int e1, int s2, int e2)
// merge 2 sorted listes, starting at s and ending in e respectively, into
// a single sorted list.
{
	Type* newArray;
	newArray = new Type[e2 - s1 + 1];    // dynamically allocate a new array

	int index1 = s1;
	int index2 = s2;
	int newIndex = 0;
	while (index1 <= e1 && index2 <= e2)
	{
		if (arry[index1] <= arry[index2])
		{
			newArray[newIndex] = arry[index1];
			index1++;
		}
		else
		{
			newArray[newIndex] = arry[index2];
			index2++;
		}
		newIndex++;
	}

	if (index1 <= e1)
	{
		for (int i = index1; i <= e1; i++)
		{
			newArray[newIndex] = arry[i];
			newIndex++;
		}
	}

	else
	{
		for (int i = index2; i <= e2; i++)
		{
			newArray[newIndex] = arry[i];
			newIndex++;
		}
	}

	// copy newArray values to input array
	for (int i = s1; i <= e2; i++)
	{
		arry[i] = newArray[i - s1];
	}

	//Free the newArray memory
	delete[] newArray;
}