Merge Sort


In [11]:
def merge(left, right): 
    
    if not len(left) or not len(right): 
        return left or right
    result = []
    i, j = 0, 0
    while (len(result) < len(left) + len(right)):
        if left[i] < right[j]:
            result.append(left[i])
            i+= 1
        else:
            result.append(right[j])
            j+= 1
        if i == len(left) or j == len(right):
            result.extend(left[i:] or right[j:])
            break 

    return result
def mergesort(arr): 
    if len(arr) < 2: 
        return arr
    middle = len(arr) // 2
    left = mergesort(arr[:middle])
    right = mergesort(arr[middle:])

    return merge(left, right)

In [12]:
import numpy as np
a = np.random.randint(100000, size=100000)
mergesort(a)


Out[12]:
[2,
 6,
 6,
 7,
 8,
 8,
 10,
 10,
 11,
 11,
 13,
 15,
 18,
 19,
 21,
 21,
 21,
 21,
 21,
 22,
 24,
 26,
 26,
 27,
 27,
 28,
 28,
 30,
 32,
 32,
 33,
 33,
 33,
 36,
 36,
 37,
 38,
 38,
 39,
 39,
 40,
 41,
 41,
 42,
 44,
 44,
 46,
 48,
 49,
 50,
 50,
 50,
 51,
 51,
 52,
 53,
 53,
 53,
 54,
 54,
 55,
 55,
 57,
 58,
 58,
 59,
 62,
 63,
 63,
 65,
 68,
 69,
 71,
 73,
 73,
 76,
 76,
 77,
 77,
 78,
 78,
 80,
 80,
 82,
 83,
 84,
 86,
 87,
 88,
 89,
 93,
 93,
 94,
 95,
 95,
 96,
 96,
 97,
 97,
 97,
 98,
 98,
 99,
 100,
 101,
 103,
 105,
 107,
 108,
 108,
 109,
 109,
 110,
 111,
 112,
 113,
 113,
 116,
 117,
 118,
 119,
 120,
 120,
 120,
 125,
 126,
 126,
 127,
 127,
 128,
 130,
 130,
 130,
 131,
 131,
 131,
 132,
 133,
 133,
 134,
 134,
 134,
 136,
 136,
 137,
 138,
 138,
 139,
 139,
 139,
 140,
 141,
 141,
 142,
 142,
 144,
 144,
 147,
 147,
 148,
 149,
 150,
 150,
 154,
 155,
 156,
 156,
 156,
 156,
 157,
 157,
 158,
 162,
 162,
 163,
 165,
 165,
 167,
 167,
 168,
 169,
 169,
 169,
 173,
 175,
 177,
 178,
 178,
 179,
 180,
 181,
 183,
 183,
 186,
 186,
 188,
 189,
 194,
 194,
 196,
 204,
 205,
 207,
 207,
 208,
 208,
 209,
 210,
 212,
 213,
 213,
 214,
 215,
 215,
 215,
 215,
 217,
 220,
 220,
 221,
 223,
 223,
 225,
 226,
 227,
 227,
 228,
 232,
 232,
 232,
 233,
 233,
 234,
 234,
 235,
 237,
 237,
 238,
 238,
 239,
 240,
 241,
 242,
 242,
 242,
 243,
 243,
 244,
 245,
 246,
 246,
 248,
 248,
 250,
 252,
 252,
 254,
 254,
 255,
 256,
 256,
 256,
 257,
 258,
 259,
 261,
 261,
 262,
 262,
 262,
 264,
 266,
 266,
 266,
 267,
 268,
 268,
 269,
 270,
 270,
 270,
 272,
 272,
 273,
 273,
 274,
 274,
 274,
 275,
 276,
 276,
 278,
 278,
 278,
 278,
 279,
 280,
 281,
 283,
 285,
 286,
 286,
 287,
 292,
 292,
 292,
 293,
 293,
 294,
 294,
 295,
 296,
 296,
 296,
 296,
 297,
 298,
 299,
 301,
 301,
 301,
 301,
 302,
 303,
 305,
 307,
 309,
 309,
 309,
 312,
 314,
 314,
 315,
 315,
 315,
 317,
 318,
 319,
 319,
 321,
 322,
 325,
 326,
 329,
 330,
 330,
 330,
 331,
 332,
 332,
 334,
 334,
 336,
 336,
 337,
 337,
 338,
 339,
 342,
 343,
 344,
 344,
 345,
 346,
 346,
 346,
 347,
 347,
 348,
 349,
 350,
 350,
 351,
 351,
 352,
 352,
 354,
 354,
 355,
 355,
 356,
 357,
 358,
 360,
 363,
 364,
 365,
 366,
 366,
 367,
 370,
 370,
 372,
 377,
 378,
 378,
 379,
 379,
 379,
 380,
 380,
 382,
 383,
 384,
 390,
 390,
 391,
 393,
 398,
 399,
 401,
 402,
 403,
 403,
 405,
 407,
 407,
 411,
 413,
 415,
 415,
 417,
 419,
 419,
 419,
 420,
 422,
 422,
 422,
 428,
 428,
 429,
 429,
 430,
 431,
 432,
 432,
 432,
 435,
 436,
 437,
 437,
 439,
 439,
 439,
 442,
 443,
 445,
 445,
 447,
 447,
 449,
 450,
 450,
 450,
 450,
 450,
 451,
 452,
 455,
 457,
 457,
 457,
 458,
 459,
 460,
 461,
 462,
 462,
 463,
 465,
 467,
 467,
 467,
 468,
 468,
 469,
 469,
 471,
 472,
 474,
 475,
 476,
 476,
 477,
 479,
 480,
 483,
 483,
 484,
 484,
 485,
 488,
 490,
 490,
 492,
 494,
 494,
 494,
 494,
 495,
 495,
 496,
 498,
 499,
 500,
 500,
 500,
 501,
 501,
 504,
 504,
 506,
 507,
 508,
 509,
 509,
 510,
 511,
 512,
 512,
 513,
 513,
 514,
 515,
 517,
 517,
 518,
 519,
 522,
 523,
 523,
 526,
 526,
 527,
 528,
 528,
 528,
 529,
 529,
 529,
 531,
 531,
 532,
 533,
 535,
 535,
 536,
 536,
 536,
 537,
 538,
 539,
 541,
 542,
 542,
 542,
 543,
 545,
 546,
 546,
 548,
 550,
 551,
 551,
 551,
 552,
 553,
 553,
 553,
 553,
 554,
 554,
 554,
 555,
 555,
 555,
 556,
 556,
 557,
 557,
 558,
 558,
 559,
 560,
 561,
 561,
 562,
 562,
 563,
 563,
 566,
 569,
 569,
 571,
 572,
 573,
 574,
 574,
 577,
 577,
 579,
 583,
 583,
 584,
 584,
 586,
 587,
 587,
 587,
 588,
 590,
 590,
 591,
 591,
 592,
 594,
 594,
 594,
 594,
 594,
 596,
 596,
 597,
 599,
 599,
 602,
 603,
 603,
 603,
 606,
 607,
 607,
 607,
 608,
 608,
 613,
 613,
 614,
 614,
 620,
 622,
 622,
 622,
 623,
 623,
 626,
 626,
 628,
 630,
 631,
 632,
 633,
 633,
 633,
 634,
 634,
 634,
 635,
 635,
 637,
 637,
 638,
 641,
 642,
 643,
 643,
 646,
 647,
 648,
 648,
 649,
 650,
 651,
 652,
 653,
 654,
 656,
 656,
 656,
 657,
 657,
 657,
 660,
 662,
 663,
 664,
 664,
 665,
 665,
 665,
 666,
 667,
 667,
 668,
 669,
 669,
 672,
 672,
 673,
 673,
 674,
 680,
 683,
 683,
 684,
 685,
 687,
 687,
 687,
 688,
 690,
 690,
 690,
 690,
 690,
 691,
 692,
 693,
 697,
 697,
 705,
 705,
 706,
 706,
 707,
 710,
 711,
 712,
 713,
 714,
 714,
 714,
 714,
 715,
 715,
 715,
 717,
 718,
 719,
 719,
 721,
 722,
 722,
 725,
 727,
 729,
 730,
 731,
 731,
 731,
 732,
 733,
 734,
 734,
 736,
 738,
 738,
 741,
 741,
 742,
 743,
 745,
 747,
 748,
 749,
 750,
 751,
 751,
 751,
 752,
 752,
 752,
 752,
 757,
 757,
 757,
 759,
 759,
 759,
 759,
 760,
 762,
 763,
 764,
 765,
 766,
 767,
 768,
 770,
 771,
 772,
 772,
 773,
 776,
 776,
 776,
 776,
 777,
 777,
 778,
 778,
 780,
 781,
 781,
 783,
 783,
 784,
 784,
 785,
 786,
 787,
 788,
 789,
 789,
 789,
 789,
 791,
 793,
 793,
 794,
 794,
 794,
 795,
 796,
 796,
 797,
 797,
 797,
 797,
 798,
 798,
 798,
 799,
 801,
 801,
 803,
 807,
 807,
 807,
 810,
 811,
 811,
 812,
 812,
 813,
 813,
 815,
 816,
 816,
 817,
 821,
 822,
 823,
 824,
 824,
 824,
 826,
 826,
 827,
 828,
 829,
 831,
 832,
 832,
 835,
 838,
 838,
 839,
 839,
 840,
 841,
 842,
 842,
 843,
 843,
 843,
 844,
 845,
 845,
 846,
 850,
 850,
 851,
 851,
 852,
 854,
 854,
 857,
 858,
 858,
 858,
 861,
 863,
 863,
 865,
 866,
 866,
 866,
 867,
 867,
 867,
 868,
 868,
 869,
 871,
 871,
 873,
 873,
 876,
 877,
 878,
 879,
 882,
 883,
 885,
 885,
 886,
 889,
 890,
 891,
 892,
 894,
 895,
 896,
 897,
 897,
 900,
 902,
 902,
 905,
 910,
 912,
 915,
 916,
 917,
 918,
 918,
 919,
 919,
 921,
 923,
 923,
 923,
 923,
 923,
 923,
 924,
 924,
 925,
 926,
 928,
 929,
 929,
 929,
 932,
 932,
 933,
 934,
 935,
 937,
 938,
 939,
 939,
 941,
 943,
 945,
 949,
 950,
 950,
 951,
 952,
 952,
 952,
 953,
 954,
 955,
 957,
 957,
 958,
 959,
 959,
 960,
 961,
 962,
 962,
 963,
 966,
 967,
 972,
 972,
 972,
 973,
 976,
 978,
 979,
 979,
 981,
 981,
 981,
 ...]

In [ ]: