Question

Overview: Implement a mergesort program using recursive function introduced in note4. Specific requirements: 1) Modify the "merge" function so that the merged list is reversed sorted. For example, if A=[3] and B=[8],C should be [8,3]. 2) The program should pop a message asking: "Please input N.". 3) The user should input an integer for N (the size of the array). 4) The program should generate N random integers, which are the initial input for sorting. 5) Implement mergesort for the N random integers. 6) After sorting, output the first five and the last five sorted elements. We will test your program using different N as inputs. Grading: 20 pts. We will test your program using 4 inputs (e.g. N=1,10,100,1000, etc.), with each input worth 5 points. Passing all gets you full credit. There are no restrictions about the data structures you use. For example, you can use array or vector. But be careful that you don't know the size of the array a prior.

Answer 1

To implement the mergesort program with the specified requirements, the following steps should be followed:

• Modify the "merge" function to merge the lists in reverse sorted order.
• Prompt the user to input the value of N.
• Take input from the user for the size of the array, N.
• Generate N random integers as the initial input for sorting.
• Implement the mergesort algorithm to sort the array.
• After sorting, output the first five and last five elements of the sorted array.

Modify the "merge" function:

1. - Instead of merging the lists in ascending order, modify the function to merge them in reverse sorted order.
2. - For example, if A=[3] and B=[8], the merged list C should be [8, 3].

Prompt user for input:

• Display a message asking the user to input the value of N.

User input:

• Accept an integer input from the user, which represents the size of the array to be sorted.

Generate random integers:

• Generate N random integers using a suitable random number generation method.
• These random integers will serve as the initial input for sorting.

Implement mergesort:

• Use a recursive function to implement the mergesort algorithm on the array.
• Split the array into smaller subarrays until each subarray contains only one element.
• Merge the subarrays in reverse sorted order until the entire array is sorted.

Output the sorted elements:

• Display the first five elements and the last five elements of the sorted array.

By following these steps, a mergesort program can be implemented to meet the specified requirements. The modified merge function ensures that the merged list is in reverse sorted order. The program prompts the user for the size of the array and generates random integers for sorting. The mergesort algorithm is then applied to sort the array, and the first five and last five elements of the sorted array are outputted.