PLEASE USE PYTHON FOR THIS ASSIGNMENT. THANK YOU!

PART2 (15 points) 1) Write programs for both insertion sort and merge sort in Python and follow the instructions below to test the programs with the provided data sets below. 2) Using your time efficiency function from HW1, Measure the execution times of both insertion and merge sorting algorithms using the attached data files (one with 1,000 integers and the other with 1.000.000 integers). 3) Count the total number of comparisons for the completion of each sorting algorithm. Here are the data files you should use: 1,000,000 integers are in rand 1000000.txt . 1.000 integers are in rand1000.txt mainly for testing purpose) . If you want to test your programs with other data sets. You can use these for the extra credit problem below. rand 10000.txt rand 100000.txt rand 250000.txt a rand500000.txt Deliverable: 1. Program source codes of both algorithms (insertion and merge sorts) 2. The summary of your test results in terms of time efficiency tested with multiple data sets (at least, 1K and 1M) for both sorting algorithms (Insertion sort and Merge sort). You may use your own time efficiency program written for HW1b to measure the time efficiencies of both sorting algorithms. Make sure your programs work well with 1K dataset before you test them with 1M one. [How to handle a long running program:) The insertion sort with 1,000,000 integers takes really long time (over 20 hours on normal personal computers). This makes it difficult to finish the slow sorting algorithm on a personal computer. Below is a way to overcome the issue. (NOTE: this workaround solution is not working on repl.it) 1). Transfer your program on to a Unix (Linux) server like csegrid machine. 2). Add the following line at the very first line of your program file and save the file. This tells Unix OS to run /user/bin/python3" with the Python script (program) in the file. "#!" in the line is called "shebang" ('sh' (Unix Bourne shell] + bang, or hash + bang) and it is used for any Unix script file (bash, perl, python, awk, ...). #!/usr/bin/python3 (You may run 'where python' command to find out the full path of python program in your environment) 3). On the command line at the input prompt, enter the following Unix command to make the file (say "insertionSort.py") executable. $ chmod +x insertion Sort.py 4). Type the following command $ nohup insertionSort.py > hw2sort.txt & OR $ nohup python insertion Sort.py > hw2sort.txt & # if you don't wan to make your program a self executable script. Adding "&" at the end of command line will make "insertionSort.py" run in the background. And ">" will redirect the output of the command to hw2sort.txt file instead of displaying it on the console. "nohup" at the beginning of the command line tells Unix OS to continue to execute the command at the background even if the current login shell ends - you either log out or disconnect from the shell and terminates your ssh login session. 5). You may also consider adding following lines to test all the data sizes in one test run for extra credit points fileNames = ["randies.txt","rand1eeee.txt", "rand1e8ee.txt","rand250888.txt","randseeeee.txt","randieeeeee.txt" 1 for name in fileNames: [your codes ..) PART 3 (10 points) Follow the guidelines below to prove that the Merge() function of your merge sort algorithm in the PART 2 is correct. 3.1 Write down general description of loop invariant technique in your own words as proof technique of correctness. (2 points) 3.2 Identify the loop invariant of the loop in your merge() function (3 points) 3.3 Describe initialization step (O points) 3.4 Describe maintenance step (4 points) 3.5 Describe Termination step (1 point) PART2 (15 points) 1) Write programs for both insertion sort and merge sort in Python and follow the instructions below to test the programs with the provided data sets below. 2) Using your time efficiency function from HW1, Measure the execution times of both insertion and merge sorting algorithms using the attached data files (one with 1,000 integers and the other with 1.000.000 integers). 3) Count the total number of comparisons for the completion of each sorting algorithm. Here are the data files you should use: 1,000,000 integers are in rand 1000000.txt . 1.000 integers are in rand1000.txt mainly for testing purpose) . If you want to test your programs with other data sets. You can use these for the extra credit problem below. rand 10000.txt rand 100000.txt rand 250000.txt a rand500000.txt Deliverable: 1. Program source codes of both algorithms (insertion and merge sorts) 2. The summary of your test results in terms of time efficiency tested with multiple data sets (at least, 1K and 1M) for both sorting algorithms (Insertion sort and Merge sort). You may use your own time efficiency program written for HW1b to measure the time efficiencies of both sorting algorithms. Make sure your programs work well with 1K dataset before you test them with 1M one. [How to handle a long running program:) The insertion sort with 1,000,000 integers takes really long time (over 20 hours on normal personal computers). This makes it difficult to finish the slow sorting algorithm on a personal computer. Below is a way to overcome the issue. (NOTE: this workaround solution is not working on repl.it) 1). Transfer your program on to a Unix (Linux) server like csegrid machine. 2). Add the following line at the very first line of your program file and save the file. This tells Unix OS to run /user/bin/python3" with the Python script (program) in the file. "#!" in the line is called "shebang" ('sh' (Unix Bourne shell] + bang, or hash + bang) and it is used for any Unix script file (bash, perl, python, awk, ...). #!/usr/bin/python3 (You may run 'where python' command to find out the full path of python program in your environment) 3). On the command line at the input prompt, enter the following Unix command to make the file (say "insertionSort.py") executable. $ chmod +x insertion Sort.py 4). Type the following command $ nohup insertionSort.py > hw2sort.txt & OR $ nohup python insertion Sort.py > hw2sort.txt & # if you don't wan to make your program a self executable script. Adding "&" at the end of command line will make "insertionSort.py" run in the background. And ">" will redirect the output of the command to hw2sort.txt file instead of displaying it on the console. "nohup" at the beginning of the command line tells Unix OS to continue to execute the command at the background even if the current login shell ends - you either log out or disconnect from the shell and terminates your ssh login session. 5). You may also consider adding following lines to test all the data sizes in one test run for extra credit points fileNames = ["randies.txt","rand1eeee.txt", "rand1e8ee.txt","rand250888.txt","randseeeee.txt","randieeeeee.txt" 1 for name in fileNames: [your codes ..) PART 3 (10 points) Follow the guidelines below to prove that the Merge() function of your merge sort algorithm in the PART 2 is correct. 3.1 Write down general description of loop invariant technique in your own words as proof technique of correctness. (2 points) 3.2 Identify the loop invariant of the loop in your merge() function (3 points) 3.3 Describe initialization step (O points) 3.4 Describe maintenance step (4 points) 3.5 Describe Termination step (1 point)