solve using insertion sort and quick sort, solve in python using 2-1 as a reference for "Q1)"

Time Efficiency program:

def time_efficiency(timer, max_time, arr_lm=0, arr_rm=0):

start_point = time.time()

if arr_lm == 0 and arr_rm == 0:

timer(max_time)

else:

timer(max_time, arr_lm, arr_rm)

end_point = time.time()

print('Timer started at: ' + str(start_point), " ", 'Timer ended at: ' + str(end_point), " ", 'Total time taken: ' + str(round(end_point - start_point, 4)), " ", 'Execution time: ' + str(round(end_point - start_point, 4)))

Data set (Just run using 1000):

348548 141913 489224 81717 403131143034 876953 784947 593480 355401200777 855598 470624 438334 967124314937 673395 78981 748181 738558160619 305980 330514 143635 269516443338 897870 533897 549242 542277730654 619923 80681 4641 945810403894 791515 299325 794329 44805274761 525591 385985 945151 992758318335 539269 903 48240 309176145343 136920 915788 283919 935245536815 503129 94206 914137 190263787092 291119 231701 970030 931558470049 439649 880473 714855 296141131667 724193 183666 219762 671025234722 212132 58329 438125 629912471040 771270 309044 534308 719407639180 502375 821615 222798 644638862752 328045 224688 58523 764998837741 73915 686332 338069 745017533314 96408 773939 708043 610224773993 329150 592823 264921 548722222130 441138 547443 38678 420518865365 116031 130389 711225 866679981546 281954 119187 700463 58139665190 473153 743441 484556 71100319190 210888 796499 803947 535263

440285 320994 650162 258383 73835650541 261577 62281 468022 816988311062 941738 188048 744102 125883364194 914160 718800 227599 31297897965 486623 795261 590148 140267649733 878486 639396 370403 767282701458 658233 633647 125115 72420321819 537104 277898 787647 810335620442 331300 572691 161194 229563318458 714783 62303 318501 414360853367 500533 410830 962526 956805801789 74166 413041 84071 963152806549 925860 622749 744235 718310829748 24965 717849 886065 17602576846 277252 141680 270449 162167556463 77905 673305 858943 11955316149 42204 115135 524940 116199231437 868990 362584 517641 73676915920 421290 250518 706739 127490217902 291774 66206 539101 242345790476 135827 165713 306289 933735156550 647179 159080 851917 145155734242 900576 620484 86229 187493512039 272256 379760 675251 197228381173 930549 909861 175805 484494411255 8688 722153 847633 721376953676 403653 744733 196539 33488

406848 453075 551457 571327 70028282253 276582 721547 704838 546156308 788562 295468 277561 20918580492 592279 634263 24326 978030138078 111288 714621 412062 964533660507 544522 500917 910320 43468409257 621725 406856 84609 45782413147 271927 311309 560863 504908234476 315054 712578 257549 168864917772 515914 245173 922920 588239157632 412447 361918 458832 613039552339 465801 88407 718179 848090120978 909832 168482 585111 390168784640 211506 886969 597079 476266903490 114164 849384 436108 321140282729 219284 972288 717365 242425996738 830896 463405 141272 1491838413 124142 858843 978633 78200877082 555392 108168 887433 68968534337 429463 942531 636997 453040275330 319179 392781 385792 251599399192 721827 601914 453774 7611882140 671045 721246 897615 19975790318 986568 863862 395094 30751671853 744989 301578 542347 391804366430 768714 802476 746151 80201751875 158667 256700 460222 29328

722494 731109 811016 536572 408615700074 667539 258397 729684 447812443526 878123 629564 759477 47204245105 153334 911223 928151 999619769032 704831 652530 322097 569704541894 450664 604904 454677 765310991815 942317 328797 943630 955249559727 256199 938021 235397 386452803307 195224 845339 8717 219876728884 868645 212804 171786 259441550266 20285 644031 959389 697422793976 821239 608683 1537 391725253160 651625 794066 749473 820208254917 342123 158240 712877 118946779810 16950 958291 986540 166713859420 384121 461440 912419 473033897947 376264 882257 581400 51538548290 560386 199254 223498 109714524952 621405 837772 947961 876792457265 855966 284709 593148 585273761726 320888 515144 321687 372108780401 769117 778166 885394 701723220277 160282 540227 516356 802959875481 448418 232030 101372 597279483791 62981 437000 452769 387637918395 29120 810701 807324 563138394391 887337 55138 154622 89650

266962 82973 579799 608740 601094455151 124830 908654 346542 739023482610 984184 944588 521983 29976445954 328643 620963 47826 489928975624 497786 219217 310999 97886197501 778465 600939 164068 57805879620 354426 249982 149914 641799376198 784111 982034 328463 580561804692 386800 73107 462716 667754244945 849019 872499 803438 441408528257 486375 851565 591824 555847241267 254007 472313 957158 358540385295 58623 609982 993668 316098592489 128619 525799 910106 135006111545 308750 27031 808001 648678396575 880909 289535 144530 6935539622 173143 850984 112555 968374132852 203134 817987 990251 629363491827 884946 24818 714733 28962828 451414 274264 291308 307570271088 247594 736508 466770 210565489972 680022 769767 613054 540072290139 465758 943775 379919 480403826616 505834 882074 809805 198484519723 53087 814200 676915 858221647267 959253 734116 924193 541948438505 791205 68008 312542 254373

581774 273083 321633 887572 725740263300 440024 297467 282412 406294340897 487342 528166 945000 3549579273 41939 183827 249127 367310607089 466094 456722 4121 846772338060 296749 104469 563504 147300221408 992447 107921 573146 5322522096 517221 322944 420865 215956909496 332854 513662 517758 698752827786 2512 589751 836665 564184896046 363654 159061 698582 885162951423 31976 33934 224155 23235977312 781162 638209 204440 309755506849 270764 83470 750244 898163204831 266343 874221 617171 466894630110 487642 476632 331109 85044182542 653469 928022 262762 16138039359 691101 256473 127036 516656178000 346663 555763 22054 600692516329 85527 15407 141317 808690804902 832471 15492 163330 104128625252 130798 881884 399661 534900879927 931953 885996 257626 2588218107 650419 392939 740448 167948323909 292434 407530 937250 603829165836 715730 820640 894743 609037741498 807343 723803 83796 417552

408518 927514 745811 857553 959521748147 153312 718015 852285 396549733072 572807 700741 716991 583513171155 837890 541863 962150 218152383399 730348 275902 784428 227393440622 646422 495155 568172 404875452897 3208 564776 650532 818300355932 63040 549971 48317 551323992325 865826 560327 620928 25327648903 95882 542793 806084 98706787743 850708 178036 259921 655358482924 480039 823285 594250 540858345141 581473 413628 114714 15384364685 496216 126144 758667 273717956736 169360 365659 279545 316953897320 34641 278217 635114 12939390956 80430 255240 900185 37401428540 192113 971039 929916 85239923107 789931 631296 48206 838294586708 16564 639987 340023 198079860762 282695 221885 468512 638321969595 655418 939530 685485 845648542615 661367 293824 31067 506172207295 537896 262157 737122 532351544227 373382 459170 574566 56463660609 824152 628700 932966 733998636064 799483 944372 760096 754081

253428 208459 355387 487647 519807603349 458506 97690 368464 215717734277 45349 145879 47165 213154140096 550263 191871 303670 981339866573 252911 466811 339655 570996367566 163613 718589 685937 782685501516 408286 769541 227082 451637310349 342819 324009 733240 978680845657 409800 767082 164835 757377584398 187702 926210 109545 520595156591 852872 191320 840631 796516

d) [10 points] Write a code combining both insertion sort and quicksort algorithms as described in Q1) to find out the most optimal k minimizing time efficiency of your algorithms using 1 M data set from HW2. You may use the time efficiency program you wrote in the previous homework. Please collect and display some performance data which proves your kis the most optimal as shown below: k-10: 11.42 seconds k-5: 11.07 seconds k: 10.55 seconds k+5: 10.59 seconds. k+10: 11.02 seconds 2-1 Insertion sort on small arrays in merge sort Although merge sort runs in (n Ign) worst-case time and insertion sort runs in (n) worst-case time, the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines. Thus, it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined. == @: def time_efficiency (timer, max_time, arr_Lm=0, arr_rm=8): start_point = time.time() if arr_lm == 0 and arr_rm timer (max_time) else: timer (max_time, arr_lm, arr_rm) end_point = time.time() print('Timer started at: + str(start_point), " ", 'Timer ended at: + str(end_point), " ", 'Total time taken: (round(end_point - start_point, 4)), " ", 'Execution time: ' + str(round(end_point - start_point, 4))) + str