Write python program for both insertion sort and merge sort.

Please show step by step explanation. Thank you.

Using your simple time efficiency function, measure the execution time of each sort algorighm using the attached data files (1000, 10000 integers in each file).

Write down general description of loop invariant technique as proof technique of correctness.

Identify the loop invariant of the loop in your merge() function

Describe the initialization step

Describe maintenance step

Describe Termination step

Note. 10000.txt is too large so I upload 1000.txt instead.

1000.txt

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

318335 539269 903 48240 309176

145343 136920 915788 283919 935245

536815 503129 94206 914137 190263

787092 291119 231701 970030 931558

470049 439649 880473 714855 296141

131667 724193 183666 219762 671025

234722 212132 58329 438125 629912

471040 771270 309044 534308 719407

639180 502375 821615 222798 644638

862752 328045 224688 58523 764998

837741 73915 686332 338069 745017

533314 96408 773939 708043 610224

773993 329150 592823 264921 548722

222130 441138 547443 38678 420518

865365 116031 130389 711225 866679

981546 281954 119187 700463 58139

665190 473153 743441 484556 71100

319190 210888 796499 803947 535263

440285 320994 650162 258383 73835

650541 261577 62281 468022 816988

311062 941738 188048 744102 125883

364194 914160 718800 227599 312978

97965 486623 795261 590148 140267

649733 878486 639396 370403 767282

701458 658233 633647 125115 724203

21819 537104 277898 787647 810335

620442 331300 572691 161194 229563

318458 714783 62303 318501 414360

853367 500533 410830 962526 956805

801789 74166 413041 84071 963152

806549 925860 622749 744235 718310

829748 24965 717849 886065 17602

576846 277252 141680 270449 162167

556463 77905 673305 858943 11955

316149 42204 115135 524940 116199

231437 868990 362584 517641 73676

915920 421290 250518 706739 127490

217902 291774 66206 539101 242345

790476 135827 165713 306289 933735

156550 647179 159080 851917 145155

734242 900576 620484 86229 187493

512039 272256 379760 675251 197228

381173 930549 909861 175805 484494

411255 8688 722153 847633 721376

953676 403653 744733 196539 33488

406848 453075 551457 571327 700282

82253 276582 721547 704838 546

156308 788562 295468 277561 209185

80492 592279 634263 24326 978030

138078 111288 714621 412062 964533

660507 544522 500917 910320 43468

409257 621725 406856 84609 457824

13147 271927 311309 560863 504908

234476 315054 712578 257549 168864

917772 515914 245173 922920 588239

157632 412447 361918 458832 613039

552339 465801 88407 718179 848090

120978 909832 168482 585111 390168

784640 211506 886969 597079 476266

903490 114164 849384 436108 321140

282729 219284 972288 717365 242425

996738 830896 463405 141272 149183

8413 124142 858843 978633 782008

77082 555392 108168 887433 68968

534337 429463 942531 636997 453040

275330 319179 392781 385792 251599

399192 721827 601914 453774 76118

82140 671045 721246 897615 19975

790318 986568 863862 395094 307516

71853 744989 301578 542347 391804

366430 768714 802476 746151 802017

51875 158667 256700 460222 29328

722494 731109 811016 536572 408615

700074 667539 258397 729684 447812

443526 878123 629564 759477 47204

245105 153334 911223 928151 999619

769032 704831 652530 322097 569704

541894 450664 604904 454677 765310

991815 942317 328797 943630 955249

559727 256199 938021 235397 386452

803307 195224 845339 8717 219876

728884 868645 212804 171786 259441

550266 20285 644031 959389 697422

793976 821239 608683 1537 391725

253160 651625 794066 749473 820208

254917 342123 158240 712877 118946

779810 16950 958291 986540 166713

859420 384121 461440 912419 473033

897947 376264 882257 581400 51538

548290 560386 199254 223498 109714

524952 621405 837772 947961 876792

457265 855966 284709 593148 585273

761726 320888 515144 321687 372108

780401 769117 778166 885394 701723

220277 160282 540227 516356 802959

875481 448418 232030 101372 597279

483791 62981 437000 452769 387637

918395 29120 810701 807324 563138

394391 887337 55138 154622 89650

266962 82973 579799 608740 601094

455151 124830 908654 346542 739023

482610 984184 944588 521983 29976

445954 328643 620963 47826 489928

975624 497786 219217 310999 978861

97501 778465 600939 164068 57805

879620 354426 249982 149914 641799

376198 784111 982034 328463 580561

804692 386800 73107 462716 667754

244945 849019 872499 803438 441408

528257 486375 851565 591824 555847

241267 254007 472313 957158 358540

385295 58623 609982 993668 316098

592489 128619 525799 910106 135006

111545 308750 27031 808001 648678

396575 880909 289535 144530 69355

39622 173143 850984 112555 968374

132852 203134 817987 990251 629363

491827 884946 24818 714733 28962

828 451414 274264 291308 307570

271088 247594 736508 466770 210565

489972 680022 769767 613054 540072

290139 465758 943775 379919 480403

826616 505834 882074 809805 198484

519723 53087 814200 676915 858221

647267 959253 734116 924193 541948

438505 791205 68008 312542 254373

581774 273083 321633 887572 725740

263300 440024 297467 282412 406294

340897 487342 528166 945000 3549

579273 41939 183827 249127 367310

607089 466094 456722 4121 846772

338060 296749 104469 563504 147300

221408 992447 107921 573146 5322

522096 517221 322944 420865 215956

909496 332854 513662 517758 698752

827786 2512 589751 836665 564184

896046 363654 159061 698582 885162

951423 31976 33934 224155 23235

977312 781162 638209 204440 309755

506849 270764 83470 750244 898163

204831 266343 874221 617171 466894

630110 487642 476632 331109 850441

82542 653469 928022 262762 161380

39359 691101 256473 127036 516656

178000 346663 555763 22054 600692

516329 85527 15407 141317 808690

804902 832471 15492 163330 104128

625252 130798 881884 399661 534900

879927 931953 885996 257626 25882

18107 650419 392939 740448 167948

323909 292434 407530 937250 603829

165836 715730 820640 894743 609037

741498 807343 723803 83796 417552

408518 927514 745811 857553 959521

748147 153312 718015 852285 396549

733072 572807 700741 716991 583513

171155 837890 541863 962150 218152

383399 730348 275902 784428 227393

440622 646422 495155 568172 404875

452897 3208 564776 650532 818300

355932 63040 549971 48317 551323

992325 865826 560327 620928 25327

648903 95882 542793 806084 98706

787743 850708 178036 259921 655358

482924 480039 823285 594250 540858

345141 581473 413628 114714 15384

364685 496216 126144 758667 273717

956736 169360 365659 279545 316953

897320 34641 278217 635114 129393

90956 80430 255240 900185 374014

28540 192113 971039 929916 85239

923107 789931 631296 48206 838294

586708 16564 639987 340023 198079

860762 282695 221885 468512 638321

969595 655418 939530 685485 845648

542615 661367 293824 31067 506172

207295 537896 262157 737122 532351

544227 373382 459170 574566 564636

60609 824152 628700 932966 733998

636064 799483 944372 760096 754081

253428 208459 355387 487647 519807

603349 458506 97690 368464 215717

734277 45349 145879 47165 213154

140096 550263 191871 303670 981339

866573 252911 466811 339655 570996

367566 163613 718589 685937 782685

501516 408286 769541 227082 451637

310349 342819 324009 733240 978680

845657 409800 767082 164835 757377

584398 187702 926210 109545 520595

156591 852872 191320 840631 796516