Natural merge sort

---NaturalMerge.java---

import java.io.PrintWriter;

import java.util.Arrays;

public class NaturalMerge {

public static void main(String[] args) {

// Test case array: A completely sorted array

int[] arr1 = { 15, 23, 23, 23, 31, 64, 77, 87, 88, 91 };

int arr1Length = arr1.length;

// Test case array: Sorted run of 3 followed by sorted run of 6

int[] arr2 = { 64, 88, 91, 12, 21, 34, 43, 56, 65 };

int arr2Length = arr2.length;

// Test case array: 5 elements in descending order, so 5 runs of length 1

int[] arr3 = { -10, -20, -30, -40, -50 };

int arr3Length = arr3.length;

// Test case array: 8 equal elements, so 1 run of 8

int[] arr4 = { -99, -99, -99, -99, -99, -99, -99, -99 };

int arr4Length = arr4.length;

// Test cases:

RunLengthTestCase[] testCases = {

// First test case uses an out-of-bounds starting index. Remaining test

// cases do not.

new RunLengthTestCase(arr1, arr1Length, arr1Length, 0),

new RunLengthTestCase(arr1, arr1Length, 0, arr1Length),

new RunLengthTestCase(arr1, arr1Length, 3, arr1Length - 3),

new RunLengthTestCase(arr2, arr2Length, 0, 3),

new RunLengthTestCase(arr2, arr2Length, 2, 1),

new RunLengthTestCase(arr2, arr2Length, 3, 6),

new RunLengthTestCase(arr3, arr3Length, 0, 1),

new RunLengthTestCase(arr3, arr3Length, 3, 1),

new RunLengthTestCase(arr4, arr4Length, 0, arr4Length),

new RunLengthTestCase(arr4, arr4Length, 4, arr4Length - 4),

new RunLengthTestCase(arr4, arr4Length, 5, arr4Length - 5)

};

// Execute each test case

PrintWriter testFeedback = new PrintWriter(System.out);

int testCasesLength = testCases.length;

for (int i = 0; i

RunLengthTestCase testCase = testCases[i];

// Execute the test case, using System.out to write messages

testCase.execute(testFeedback);

}

testFeedback.flush();

// Test case array for sorting

int[] arr5 = { 92, 71, 18, 26, 54, 73, 89, 10, 39, 99, 64, 22 };

int arr5Length = arr5.length;

int[] arr5Copy = new int[arr5Length];

for (int i = 0; i

arr5Copy[i] = arr5[i];

}

NaturalMergeSorter sorter = new NaturalMergeSorter();

sorter.naturalMergeSort(arr5Copy, arr5Length);

System.out.print(" ");

System.out.print((IsArraySorted.isSorted(arr5Copy, arr5Length) ? "PASS" : "FAIL"));

System.out.print(": naturalMergeSort()");

System.out.print(" ");

System.out.print(" Array before calling naturalMergeSort(): " + Arrays.toString(arr5));

System.out.print(" ");

System.out.print(" Array after calling naturalMergeSort(): " + Arrays.toString(arr5Copy));

System.out.print(" ");

}

}

---NaturalMergeSorter.java---

public class NaturalMergeSorter {

public int getSortedRunLength(int[] array, int arrayLength,

int startIndex) {

// Your code here

}

public void naturalMergeSort(int[] array, int arrayLength) {

// Your code here

}

public void merge(int[] numbers, int leftFirst, int leftLast,

int rightLast) {

int mergedSize = rightLast - leftFirst + 1;

int[] mergedNumbers = new int[mergedSize];

int mergePos = 0;

int leftPos = leftFirst;

int rightPos = leftLast + 1;

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

while (leftPos

if (numbers[leftPos]

mergedNumbers[mergePos] = numbers[leftPos];

leftPos++;

}

else {

mergedNumbers[mergePos] = numbers[rightPos];

rightPos++;

}

mergePos++;

}

// If left partition isn't empty, add remaining elements to mergedNumbers

while (leftPos

mergedNumbers[mergePos] = numbers[leftPos];

leftPos++;

mergePos++;

}

// If right partition isn't empty, add remaining elements to mergedNumbers

while (rightPos

mergedNumbers[mergePos] = numbers[rightPos];

rightPos++;

mergePos++;

}

// Copy merged numbers back to numbers

for (mergePos = 0; mergePos

numbers[leftFirst + mergePos] = mergedNumbers[mergePos];

}

// Free temporary array

mergedNumbers = null;

}

}

---RunLengthTestCase.java---

import java.io.PrintWriter;

import java.util.Arrays;

// RunLengthTestCase represents a test case for the NaturalMergeSorter class's

// getSortedRunLength() function.

public class RunLengthTestCase {

public int[] array;

public int arrayLength;

public int startIndex;

public int expectedReturnValue;

public RunLengthTestCase(int[] array, int len, int start,

int expectedRet) {

this.array = array;

arrayLength = len;

startIndex = start;

expectedReturnValue = expectedRet;

}

// Executes the test case. If the test case passes, a message that starts

// with "PASS" is printed and true is returned. Otherwise a message that

// starts with "FAIL" is printed and false is returned.

public final boolean execute(PrintWriter testFeedback) {

// Create a NaturalMergeSorter instance

NaturalMergeSorter userSorter = new NaturalMergeSorter();

// Call the getSortedRunLength() method with the test case parameters

int userRetVal = userSorter.getSortedRunLength(

array, arrayLength, startIndex);

// The test passed only if the actual return value equals the expected

// return value

final boolean passed = (userRetVal == expectedReturnValue);

// Show a message about the test case's results

if(passed) {

testFeedback.write("PASS: ");

}

else {

testFeedback.write("FAIL: ");

}

testFeedback.write("getSortedRunLength()" + " ");

testFeedback.write(" Array: " + Arrays.toString(array) + " ");

testFeedback.write(" Start index: " + startIndex + " ");

testFeedback.write(" Expected return value: " + expectedReturnValue);

testFeedback.write(" ");

testFeedback.write(" Actual return value: " + userRetVal + " ");

return passed;

}

// Writes comma-separated elements to PrintWriter

public final void writeArray(PrintWriter output) {

// Output occurs only if at least one array element exists

if (arrayLength > 0)

{

// Write the first element without a comma

output.write("" + array[0]);

// Write each remaining element preceded by a comma

for (int i = 1; i

output.write(", " + array[i]);

}

}

}

}

---IsArraySorted.java---

public class IsArraySorted {

public static boolean isSorted(int[] arr, int arrSize) {

for (int i = 1; i

if (arr[i]

return false;

}

}

return true;

}

}

The merge sort algorithm recursively divides the array in half until an array with one element is reached. A variant of merge sort, called natural merge sort, instead finds already-sorted runs of elements and merges the runs together. Ex: The unsorted array below has five sorted runs. Natural merge sort starts at index 0 and finds sorted runs A and B. Runs A and B are merged, using the same merging algorithm as merge sort, to make run F. Next, the algorithm starts after the merged part F, again looking for two sequential, sorted runs. Runs C and D are found and merged to make run G. The algorithm then starts after the merged portion G. Only one run exists, run E, until the end of the array is reached. So the algorithm starts back at index 0 , finds runs F and G, and merges to make run H. Again a single run is found after the just-merged part, so the search starts back at index 0 . Runs H and E are found and merged. One last search for a sorted run occurs, finding a sorted run length equal to the array's length. So the array is sorted and the algorithm terminates. Step 1: Implement the getSortedRunLength() method Implement the getSortedRunLength() method in NaturalMergeSorter.java. Access NaturalMergeSorter.java by clicking on the orange arrow next to NaturalMerge.java at the top of the coding window. getSortedRunLength0 has three parameters: - array: a reference to an array of integers, - arrayLength: an integer for the array's length, and - startIndex: an integer for the run's starting index. The method returns the number of array elements sorted in ascending order, starting at startlndex and ending either at the end of the sorted run, or the end of the array, whichever comes first. The method returns 0 if startlndex is out of bounds. File NaturalMerge.java has several test cases for getSortedRunLength0 that can be run by clicking the "Run program" button. One test case also exists for naturalMergeSort 0 , but that can be ignored until step two is completed. The program's output does not affect grading. Submit for grading to ensure that the getSortedRunLength() unit tests pass before proceeding. Step 2: Implement the naturalMergeSort() method Implement the naturalMergeSort) method in NaturalMergeSorter.java. naturalMergeSort() must: 1. Start at index i=0 2. Get the length of the first sorted run, starting at i Return if the first run's length equals the array length If the first run ends at the array's end, reassign i=0 and repeat step 2 3. Get the length of the second sorted run, starting immediately after the first 4. Merge the two runs with the provided merge0 method 5. Reassign i with the first index after the second run, or 0 if the second run ends at the array's end 6. Go to step 2 459428.2988902.q3zqy7 \begin{tabular}{l|l} LAB & 3.16.1: LAB: Natural merge sort \end{tabular} Downloadable files Current file: The merge sort algorithm recursively divides the array in half until an array with one element is reached. A variant of merge sort, called natural merge sort, instead finds already-sorted runs of elements and merges the runs together. Ex: The unsorted array below has five sorted runs. Natural merge sort starts at index 0 and finds sorted runs A and B. Runs A and B are merged, using the same merging algorithm as merge sort, to make run F. Next, the algorithm starts after the merged part F, again looking for two sequential, sorted runs. Runs C and D are found and merged to make run G. The algorithm then starts after the merged portion G. Only one run exists, run E, until the end of the array is reached. So the algorithm starts back at index 0 , finds runs F and G, and merges to make run H. Again a single run is found after the just-merged part, so the search starts back at index 0 . Runs H and E are found and merged. One last search for a sorted run occurs, finding a sorted run length equal to the array's length. So the array is sorted and the algorithm terminates. Step 1: Implement the getSortedRunLength() method Implement the getSortedRunLength() method in NaturalMergeSorter.java. Access NaturalMergeSorter.java by clicking on the orange arrow next to NaturalMerge.java at the top of the coding window. getSortedRunLength0 has three parameters: - array: a reference to an array of integers, - arrayLength: an integer for the array's length, and - startIndex: an integer for the run's starting index. The method returns the number of array elements sorted in ascending order, starting at startlndex and ending either at the end of the sorted run, or the end of the array, whichever comes first. The method returns 0 if startlndex is out of bounds. File NaturalMerge.java has several test cases for getSortedRunLength0 that can be run by clicking the "Run program" button. One test case also exists for naturalMergeSort 0 , but that can be ignored until step two is completed. The program's output does not affect grading. Submit for grading to ensure that the getSortedRunLength() unit tests pass before proceeding. Step 2: Implement the naturalMergeSort() method Implement the naturalMergeSort) method in NaturalMergeSorter.java. naturalMergeSort() must: 1. Start at index i=0 2. Get the length of the first sorted run, starting at i Return if the first run's length equals the array length If the first run ends at the array's end, reassign i=0 and repeat step 2 3. Get the length of the second sorted run, starting immediately after the first 4. Merge the two runs with the provided merge0 method 5. Reassign i with the first index after the second run, or 0 if the second run ends at the array's end 6. Go to step 2 459428.2988902.q3zqy7 \begin{tabular}{l|l} LAB & 3.16.1: LAB: Natural merge sort \end{tabular} Downloadable files Current file