I need help with this lab!

You only have to modify MergeSortOptimized, and SortBenchmark!

MergeSortOptimized.java:

public class MergeSortOptimized implements Sorter { @Override public void sort(int[] array) { // TODO: Allocate the scratch-space buffer here and pass it to all subsequent methods. // That way they are reusing the same memory. // The scratch space will need to be same length as the input array. mergeSort(array, 0, array.length - 1); } // TODO: Add a parameter to this method for the scratch space array. private static void merge(int[] numbers, int start, int middle, int end) { int mergedSize = end - start + 1; // Size of merged partition // TODO: Remove this allocation and use the scratch-space array instead. int[] mergedNumbers = new int[mergedSize]; // Dynamically allocates temporary // array for merged numbers int mergePos = 0; // Position to insert merged number int leftPos = start; // Initialize left partition position int rightPos = middle + 1; // Initialize right partition position // Add smallest element from left or right partition to merged numbers while (leftPos

// TODO: Add a parameter to this method for the scratch-space array. private static void mergeSort(int[] numbers, int start, int end) { if (start

sorter.java public interface Sorter { void sort(int[] array); }

TestMergeSortOptimized.java

public class TestMergeSortOptimized extends TestSorterBase { @Override protected Sorter makeSorter() { return new MergeSortOptimized(); } }

TestSorterBase.java

import org.junit.jupiter.api.Test;

// This class is abstract. We subclass to test a specific kind of sorting. abstract class TestSorterBase {

protected abstract Sorter makeSorter(); void assertIsSorted(int[] array) { for (int i = 0; i

}

SortBenchMark:

import java.util.Arrays;

public class SortBenchmark { static void benchmarkSort(int[] array, Sorter sorter) { long startTime = System.currentTimeMillis(); for (int i = 0; i

benchmarkSort(array, new MergeSort()); } }

MergeSort.java

public class MergeSort implements Sorter { @Override public void sort(int[] array) { mergeSort(array, 0, array.length - 1); }

private static void merge(int[] numbers, int start, int middle, int end) { int mergedSize = end - start + 1; // Size of merged partition int[] mergedNumbers = new int[mergedSize]; // Dynamically allocates temporary // array for merged numbers int mergePos = 0; // Position to insert merged number int leftPos = start; // Initialize left partition position int rightPos = middle + 1; // Initialize right partition position

// Add smallest element from left or right partition to merged numbers while (leftPos

// If left partition is not empty, add remaining elements to merged numbers while (leftPos

// If right partition is not empty, add remaining elements to merged numbers while (rightPos

// Copy merged numbers back to numbers for (mergePos = 0; mergePos

private static void mergeSort(int[] numbers, int start, int end) { if (start

// Recursively sort left and right partitions mergeSort(numbers, start, middle); mergeSort(numbers, middle + 1, end);

// Merge left and right partition in sorted order merge(numbers, start, middle, end); } } }

For this lab you will be modifying the merge sort implementation we covered in class to attempted to improve it's performance. You can download the starter file MergeSortOptimized.java and follow the TODO messages to implement the changes. You'll also need to make that file compile. After you've implemented those changes, you can use TestMergeSortOptimized.java and TestSorterBase.java to check that your modified implementation still sorts correctly. (You'll have to add both files to your project to be able to run the tests). After you've tested your implementation, modify SortBenchmark.java to compare the performance of the new version of the merge sort against the old version (MergeSort.java ). Finally, add a comment at the top of MergeSortOptimized.java answering the following questions: 1. How much of an increase or decrease in performance did you see when you compared the original merge sort against the modified version? 2. How did the changes you made to the code lead to that change in performance? Turn in both MergeSortOptimized.java and your modified SortBenchmark.java