Analysis of Insertion Sort

Like selection sort, insertion sort loops over the indices of the array. It just calls insert on the elements at indices $1,2,3,…,n−1$. Just as each call to indexOfMinimum took an amount of time that depended on the size of the sorted subarray, so does each call to insert. Actually, the word "does" in the previous sentence should be "can," and we'll see why.

Let's take a situation where we call insert and the value being inserted into a subarray is less than every element in the subarray. For example, if we're inserting $0$ into the subarray $[2, 3, 5, 7, 11]$, then every element in the subarray has to slide over one position to the right. So, in general, if we're inserting into a subarray with $k$ elements, all $k$ might have to slide over by one position. Rather than counting exactly how many lines of code we need to test an element against a key and slide the element, let's agree that it's a constant number of lines; let's call that constant $c$. Therefore, it could take up to $c⋅k$ lines to insert into a subarray of $k$ elements.

Suppose that upon every call to insert, the value being inserted is less than every element in the subarray to its left. When we call insert the first time, $k=1$. The second time, $k=2$. The third time, $k=3$. And so on, up through the last time, when $k=n−1$. Therefore, the total time spent inserting into sorted subarrays is