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 the time efficiency function, 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 rand1000000.txtPreview the document , 1,000 integers are in rand1000.txtPreview the document (mainly for testing purpose)

Deliverable:

Program source codes of both algorithms (insertion and merge sorts) 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). Make sure your programs work well with 1K dataset before you test them with 1M one.

rand1000000.txt (This file should contain 100000 integers)

Please make a new .txt file and copy and paste these numbers as I can't attach any files in this post. 355934 37735 968741 107465 800642 78155 495634 746343 653258 716358 454146 66248 348034 248819 83678 52134 842713 607454 909044 379401 932934 152622 243745 989752 527633 883309 935772 223416 186226 300332 355683 450334 667534 862435 295740 331439 444506 331374 685484 415773 346845 454474 453580 264625 33177 233401 612309 161726 227479 391749 542772 584081 752375 600953 621108 474414 30825 356503 491007 431274 163780 572156 50856 187718 216691 334411 151996 992263 627303 491255 437057 847086 60635 811532 845422 395974 562664 370313 985918 336839 177581 975600 788800 446104 734892

rand1000.txt (This file should contain 1000 integers)

Please make a new .txt file and copy and paste these numbers as I can't attach any files in this post. 348548 141913 489224 81717 403131 143034 876953 784947 593480 355401 200777 855598 470624 438334 967124 314937 673395 78981 748181 738558 160619 305980 330514 143635 269516 443338 897870 533897 549242 542277 730654 619923 80681 4641 945810 403894 791515 299325 794329 44805 274761 525591 385985 945151 992758