Question

Trace the complete execution of the MergeSort algorithm when called on the array of integers, numbers, below. Show the resulting sub-arrays formed after each call to merge by enclosing them in { }. For example, if you originally had an array of 5 elements, a = {5,2,8,3,7}, the first call to merge would result with: {2, 5} 8, 3, 7 ← Note after the first call to merge, two arrays of size 1 have been merged into the sorted subarray {2,5} and the values 2 and 5 are sorted in array a You are to do this trace for the array, numbers, below. Be sure to show the resulting sub-arrays after each call to MergeSort. int[] numbers = {23, 14, 3, 56, 17, 8, 42, 18, 5};

Answer 1

public class Main {

public static void merge(int[] arr, int l, int m, int r) {

int n1 = m - l + 1;

int n2 = r - m;

int[] L = new int[n1];

int[] R = new int[n2];

for (int i = 0; i < n1; ++i)

L[i] = arr[l + i];

for (int j = 0; j < n2; ++j)

R[j] = arr[m + 1 + j];

int i = 0, j = 0;

int k = l;

while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];

i++;

} else {

arr[k] = R[j];

j++;

}

k++;

}

while (i < n1) {

arr[k] = L[i];

i++;

k++;

}

while (j < n2) {

arr[k] = R[j];

j++;

k++;

}

printArray(arr, l, r);

}

public static void sort(int[] arr, int l, int r) {

if (l < r) {

int m = (l + r) / 2;

sort(arr, l, m);

sort(arr, m + 1, r);

merge(arr, l, m, r);

}

}

static void printArray(int[] arr, int l, int r) {

System.out.print("{");

for (int i = l; i <= r; ++i)

System.out.print(arr[i] + " ");

System.out.println("}");

}

public static void main(String[] args) {

int[] arr = {23, 14, 3, 56, 17, 8, 42, 18, 5};

sort(arr, 0, arr.length - 1);

}

}

Step-by-step explanation:

See answer