Question

You’ve done merge (on Lists), so now it’s time to do merge sort (on arrays). Create a public non-final class named MergeSort that extends Merge. Implement a public static method int[] mergesort(int[] values) that returns the input array of ints sorted in ascending order. You will want this method to be recursive, with the base case being an array with zero or one value. If the passed array is null you should return null. If the passed array is empty you should return an empty array. You do not have to sort the array in place, but the returned array does not have to be a copy. To help you your parent class Merge provides two useful class methods: int[] merge(int[] first, int[] second): this merges two sorted arrays into a second sorted array. If either array is null it returns null, so you should not call it on a null array. int[] copyOfRange(int[] original, int from, int to): this acts as a wrapper on Arrays.copyOfRange, accepting the same arguments and using them in the same way. (You can’t use java.util.Arrays in this problem for reasons that will become obvious if you inspect the rest of the documentation…​) Note that the test code will test that you call merge an appropriate number of times, so you should call it to join single-element arrays together.

Answer 1

Check the explanation

Step-by-step explanation:

/* Java program for Merge Sort */

class MergeSort

{

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

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

{

// Find sizes of two subarrays to be merged

int n1 = m - l + 1;

int n2 = r - m;

/* Create temp arrays */

int L[] = new int [n1];

int R[] = new int [n2];

/*Copy data to temp arrays*/

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];

/* Merge the temp arrays */

// Initial indexes of first and second subarrays

int i = 0, j = 0;

// Initial index of merged subarry array

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++;

}

/* Copy remaining elements of L[] if any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy remaining elements of R[] if any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

// Main function that sorts arr[l..r] using

// merge()

void sort(int arr[], int l, int r)

{

if (l < r)

{

// Find the middle point

int m = (l+r)/2;

// Sort first and second halves

sort(arr, l, m);

sort(arr , m+1, r);

// Merge the sorted halves

merge(arr, l, m, r);

}

}

/* A utility function to print array of size n */

static void printArray(int arr[])

{

int n = arr.length;

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

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

System.out.println();

}

// Driver method

public static void main(String args[])

{

int arr[] = {12, 11, 13, 5, 6, 7};

System.out.println("Given Array");

printArray(arr);

MergeSort ob = new MergeSort();

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

System.out.println("\\Sorted array");

printArray(arr);

}

}

/* This code is contributed by Rajat Maurya */

Answer 2

Kindly check explaination for code

Step-by-step explanation:

/* Java program for Merge Sort */

class MergeSort

{

// Merges two subarrays of arr[].

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

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

{

// Find sizes of two subarrays to be merged

int n1 = m - l + 1;

int n2 = r - m;

/* Create temp arrays */

int L[] = new int [n1];

int R[] = new int [n2];

/*Copy data to temp arrays*/

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];

/* Merge the temp arrays */

// Initial indexes of first and second subarrays

int i = 0, j = 0;

// Initial index of merged subarry array

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++;

}

/* Copy remaining elements of L[] if any */

while (i < n1)

{

arr[k] = L[i];

i++;

k++;

}

/* Copy remaining elements of R[] if any */

while (j < n2)

{

arr[k] = R[j];

j++;

k++;

}

}

// Main function that sorts arr[l..r] using

// merge()

void sort(int arr[], int l, int r)

{

if (l < r)

{

// Find the middle point

int m = (l+r)/2;

// Sort first and second halves

sort(arr, l, m);

sort(arr , m+1, r);

// Merge the sorted halves

merge(arr, l, m, r);

}

}

/* A utility function to print array of size n */

static void printArray(int arr[])

{

int n = arr.length;

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

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

System.out.println();

}

// Driver method

public static void main(String args[])

{

int arr[] = {12, 11, 13, 5, 6, 7};

System.out.println("Given Array");

printArray(arr);

MergeSort ob = new MergeSort();

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

System.out.println("\\Sorted array");

printArray(arr);

}

}