Part A: Implement recursive merge sort -70 points

Part B: Terminate the recursion for merge sort, when the size of the segment is at most 8 (H L 8), and then use insertion sort -30 points

For part A write a program for merge sort using C/C++ programming language. Take your array size to be 1000.You should use recursive Merge sort. For part B combine merge sort with insertion sort. You should terminate the recursion for merge sort, when the size of the segment is at most 8 (H L 8), and then use insertion sort. You can use the merge code, and insertion sort (if any) from the text book, but the remaining code should be written by yourself. Your program should read from a file called data1.txt and write to a file called out1.txt. ALL programs must run on the CSE machines. No credit will be given to programs that would not compile or run on the CSE machines. Your program must sort the numbers in each line in the input file. You should follow the best practices in writing your code. Include source code and a read me file with all the necessary information about the program and yourself to allow the grader to run your programs on CSE machines and to identify you. You should submit the entire source code and readme file through Blackboard.

Example input:

2.5 600 -2 100

200 400 20.57 36

Example Output:

-2 2.5 100 600

20.57 36 200 400