Iterative Merge Sort You will implement a bottom up iterative version of merge sort. The algorithm works as follows. Instead of recursively dividing, think about how you can divide the array using a for loop. You can think of each individual element in the array as already sorted. You are free to reuse the merge function from either Homework 2 or Homework 4. Use the following example to help guide you. 7 4 3 1 4 7 4 2 9 3 7 3 3 9 9 4 2 5 2 1 31 5 LO 5 2 6 1 1 5 7 6 Before Iteration 1 6 Before Iteration 2 6 Before Iteration 3 8 After Iteration 3 The first iteration of the loop will merge all pairs of elements to make 4 sorted pairs The second iteration will merge each pair of element to make two sorted groups of 4 The third iteration will merge each group of 4 sorted elements.
Below is method signature class:
package hW7;
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr) {
}
}
and below is from homework 4 merge function:
public static void mergeSort(int [] arr) {
mergeSortRecurse(arr,0,arr.length-1);
}
private static void mergeSortRecurse(int[] arr, int start, int end) {
if(start>=end)
return;
int mid = start + ((end-start)/2);
mergeSortRecurse(arr,start,mid);
mergeSortRecurse(arr,mid+1,end);
merge(arr,start,mid,end);
}
private static void merge(int[] arr, int start, int mid, int end) {
int leftSize = mid - start +1;
int rightSize = end - mid;
int[] left = new int[leftSize+1];
int[] right = new int[rightSize+1];
int leftIndex;
int rightIndex;
for(leftIndex = 0; leftIndex<leftSize;leftIndex++)
left[leftIndex] = arr[start+leftIndex];
for(rightIndex = 0; rightIndex<rightSize;rightIndex++)
right[rightIndex] = arr[mid+rightIndex+1];
left[leftIndex] = Integer.MAX_VALUE;
right[rightIndex] = Integer.MAX_VALUE;
leftIndex = 0;
rightIndex = 0;
for(int mergeIndex = start; mergeIndex<=end;mergeIndex++) {
if(left[leftIndex] <= right[rightIndex]) {
arr[mergeIndex] = left[leftIndex];
leftIndex++;
}
else {
arr[mergeIndex] = right[rightIndex];
rightIndex++;
}
}
}
Trending now
This is a popular solution!
Step by step
Solved in 5 steps with 2 images
