This lab will test your implementation of insertionSortNM. See the assignment PDF on D2L for full details.

You can pattern your insertionSortNM after the insertionSort we did in class, or the version in the book. I've provided a version of StdArray that contains a swap() function (use that in place of the author's exch() function), and I've included a version of less() in the StdSort template that I provided.

The test program creates a small array and tests it for various values of m.

The version of StdArray that I provided also contains implementations of upperBound() and rotateRight().

-----------------------------------------------------------------------------------------

public class StdArray {

public static void swap(T[] a, int idx1, int idx2) {

T t = a[idx1];

a[idx1] = a[idx2];

a[idx2] = t;

}

// Returns index of first element strictly greater than key.

//

// Preconditions:

// 0

// a != null or lo == hi

// a[lo,hi) != null

// a is sorted

// Postconditions (let ret be the return value):

// a is unchanged

// lo

// a[lo,ret) key

public static > int upperBound(T[] a, int lo, int hi, T key) {

while (lo

// lo' is the original value of lo

// hi' is the original value of hi

// a[lo',lo) key

int mid = lo + (hi - lo) / 2;

if (a[mid].compareTo(key)

lo = mid + 1;

else

hi = mid;

}

// a[lo',ret) key

return lo;

}

public static > int upperBound(T[] a, T key) {

return upperBound(a, 0, a.length, key);

}

public static void rotateRight(T[] a, int lo, int hi) {

T t = a[--hi];

for (int i = hi; i > lo; i--)

a[i] = a[i-1];

a[lo] = t;

}

public static void rotateRight(T[] a) {

rotateRight(a, 0, a.length);

}

public static > boolean isSorted(T[] a) {

for (int i = 1; i

if (a[i-1].compareTo(a[i]) > 0)

return false;

return true;

}

}

--------------------------------------------------------------------------------------------

Current file: StdSort.java Load default template... 1 public class StdSort { 3 4. public static > void insertionsortNM(T[] a, int n, int m) /I Your code goes here. 8 I 've included insertionSort for reference. public static > boolean less(T a, Tb) 18 19 28 return a.compareTo(b) e