Question

Merge Sort - Arrays
Implement Merge Sort using arrays. Apply Divide and Conquer algorithm design strategy .It divides input array into two halves until each half contains single element and then merges these two sorted halves.

Note:

If the size of the array is less than or equal to 0 then print "Invalid array size" and terminate the program.

Implement the main() inside the class 'MergeSortDriver'



Functions to be used:

public static void merge() - function is used for merging two halves.

public static void mergeSort(int[] arr, int l, int r) - 'l' represents left index and 'r' represents the right index of the sub-array of 'arr' to be sorted.

Sample Input/Output 1:

Enter the size of an array:5

Enter the elements:3

1

2

8

6

Given array is

3 1 2 8 6

Sorted array is

1 2 3 6 8

Sample Input/Output 2:

Enter the size of an array:0

Invalid array size

Answer 1

Answer:

In merge sort, the array is split in half recursively until each sub-array has one element, at which point the sub-arrays are merged to create the sorted array. With the assumption that array[l.. n] and arr[n+1.. r] are sorted, the merge() method joins two sorted sub-arrays into one.

Explanation:

In merge sort, the array is split in half recursively until each sub-array has one element, at which point the sub-arrays are merged to create the sorted array. With the assumption that array[l.. n] and arr[n+1.. r] are sorted, the merge() method joins two sorted sub-arrays into one.

l is the index of the first element and r is the index of the final element in the formula MergeSort(arr[], l, r]).

If r > l

1. To divide an array into two equal halves, locate its middle index:

m = (l+r)/2

2. Dial MergeSort during the opening period:

mergeSort (array, l, m)

3. Telephone mergeSort for the back half:

array.mergeSort(m+1, r)

4. Recursively combine the two parts such that only one sorted half remains.

#SPJ3