Implement the sort method of the merge sort algorithm without recursion, where the length of the array is a power of 2. Keep merging adjacent regions whose size is a power of 2.

Bonus Change your algorithm so that it works on input arrays that have an arbitrary length. You will need to pay special attention to the last sub-array on each pass that is not a power of 2.

You will need nested loops to complete this lab. The outermost loop will continue while our sub-array size is less than or equal to the length of the input array (You could also define it to run until less than the length of the input array it depends on how your inner loop is defined). The second loop will need to process adjacent sub-arrays by calling merge on each pair of adjacent sub-arrays. (Note that we are not actually creating sub-arrays here, we are simply keeping track of indexes into our array to logically split it into sub-arrays).

Here is a sample run from a working project:

Unsorted:

[69, 79, 38, 49, 90, 86, 46, 18, 97, 11, 24, 86, 82, 92, 13, 98]

Sorted:

[11, 13, 18, 24, 38, 46, 49, 69, 79, 82, 86, 86, 90, 92, 97, 98]

Currently I have 3 classes that each have their own started codeArrayUtil, MergeSorter, and MergeSortDemo

ArrayUtil starter code:

import java.util.Random; /** * This class contains utility methods for array manipulation. */ public class ArrayUtil { private static Random generator = new Random(); /** * Creates an array filled with random values. * * @param length * the length of the array * @param n * the number of possible random values * @return an array filled with length numbers between 0 and n - 1 */ public static int[] randomIntArray(int length, int n) { int[] a = new int[length]; for (int i = 0; i < a.length; i++) { a[i] = generator.nextInt(n); } return a; } /** * Swaps two entries of an array. * * @param a * the array * @param i * the first position to swap * @param j * the second position to swap */ public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } } 

MergeSortDemo starter code:

import java.util.Arrays;

/** * This program demonstrates the merge sort algorithm by sorting an array that * is filled with random numbers. */ public class MergeSortDemo { public static void main(String[] args) { // make an array with a size of a power of 2 int[] a = ArrayUtil.randomIntArray((int) Math.round(Math.pow(2, 4)), 100); System.out.println("Unsorted: "); System.out.println(Arrays.toString(a));

MergeSorter.sort(a); System.out.println("Sorted: "); System.out.println(Arrays.toString(a)); } }

MergeSorter starter code:

/** * This class sorts an array, using the merge sort algorithm non-recursively. */ public class MergeSorter { //******* COMPLETE THIS METHOD ********// public static void sort(int[] a) { } //***** You do not need to change this method *****// //***** You do need to understand this method *****// public static void merge(int from, int mid, int to, int[] a) { // Size of the range to be merged int n = to - from + 1; // Merge both halves into a temporary array b int[] b = new int[n]; // Next element to consider in the first half int i1 = from; // iFirst from book // Next element to consider in the second half int i2 = mid + 1; // iSecond from book int j = 0; // Next open position in b // As long as neither i1 nor i2 past the end, move // the smaller element into b while (i1 <= mid && i2 <= to) { if (a[i1] < a[i2]) { b[j] = a[i1]; i1++; } else { b[j] = a[i2]; i2++; } j++; } // Note that only one of the two while loops // below is executed // Copy any remaining entries of the first half while (i1 <= mid) { b[j] = a[i1]; i1++; j++; } // Copy any remaining entries of the second half while (i2 <= to) { b[j] = a[i2]; i2++; j++; } // Copy back from the temporary array for (j = 0; j < n; j++) { a[from + j] = b[j]; } } }