Code for Insertion Sort

Source: Data Abstraction and Problem Solving with C++: Walls and Mirrors, Seventh Edition, by Frank M. Carrano and Timothy Henry, Addison Wesley, 2017.

Here is a paraphrase of Carrano's code for insertion sort. He expresses it as a template function, but for the homework, it should not be a template.

	template <typename T>
	void insertionSort(T theArray[], int n)
	{
	    for (int unsorted = 1; unsorted < n; unsorted++)
	    {
	        T nextItem = theArray[unsorted];
	        int loc = unsorted;
	        while (loc > 0  &&  theArray[loc-1] > nextItem)
		{
		    theArray[loc] = theArray[loc-1];
		    loc--;
		}
	        theArray[loc] = nextItem;
	    }
	}