Rewrite insertion sort so that, instead of building the sorted part at the beginning of the array, it builds it at the end of the array (so the unsorted part will always be to the left of the sorted part instead of the other way around).What are the time and space complexities for this implementation? Explain.

Question

What will be an ideal response?

Answer 1

```
Solution is below and also with the Instructor’s code.
The cost is the same as for the ascending order implementation.

/**
* Sort an array of integers in non-increasing order using insertion sort.
* @param a the array of integers to sort
* @throws NullPointerException if the array object is null
*/
public static void insertionSort( int[] a ) {
int target; // the element we want to insert
int targetPos; // position of the first element of the unsorted section
int pos;

if ( a == null ) {
throw new NullPointerException();
}

// while the size of the unsorted section is greater than 0
// when targetPos reaches -1, there are no more unsorted elements
for ( targetPos = a.length - 2; targetPos >= 0; targetPos-- ) {
// get a copy of the last element in the unsorted section
target = a[targetPos];

// while there are elements in the unsorted section to examine AND
// we haven't found the insertion point for target
for ( pos = targetPos + 1; ( pos < a.length ) &&
( a[pos] < target ); pos++ ) {
// the element at pos is < target, so move it down in the array
a[pos - 1] = a[pos];
}
// loop postcondition: pos == a.length or a[pos] >= target,
// so pos - 1 is the new home for target

// insert target in its final sorted position
a[pos - 1] = target;
}
}

```