get the list to sort
make a new, empty list
loop over each item in the list to sort:
- loop over each item in the new list:
- if the current place in the new list is empty:
  - set it equal to the current test item
- if the current place in the new list is greater than the current test item:
  - loop over the new list, moving each item up one place
    - set the current place in the new list to the test item

I think this is called an insertion sort



In [101]:

    
def list_sort(input_list):
    output_list=[]
    for input_item in input_list:
        if not output_list:
            output_list.append(input_item)
        else:
            index=0
            for a in range(len(output_list)):
                if output_list[index]<input_item:
                    index+=1
            if index==len(output_list):
                output_list.append(input_item)
            else:
                first_half=output_list[:index]
                first_half.append(input_item)
                last_half=output_list[index:]
                output_list=first_half+last_half
    return output_list



In [109]:

    
def random_list_maker(list_len):
    from random import randint
    return_list=[]
    for i in range(list_len):
        return_list.append(randint(0,999))
    return return_list



In [110]:

    
%time list_sort(random_list_maker(10))









    



CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 86.8 µs






    Out[110]:





[136, 290, 381, 423, 456, 521, 533, 696, 869, 995]



In [111]:

    
%time list_sort(random_list_maker(100))









    



CPU times: user 0 ns, sys: 0 ns, total: 0 ns
Wall time: 738 µs






    Out[111]:





[3,
 14,
 32,
 45,
 48,
 52,
 88,
 117,
 118,
 121,
 154,
 166,
 173,
 183,
 203,
 215,
 221,
 226,
 227,
 236,
 237,
 245,
 268,
 281,
 283,
 291,
 293,
 301,
 319,
 320,
 358,
 363,
 373,
 378,
 379,
 382,
 396,
 406,
 412,
 460,
 482,
 502,
 511,
 524,
 531,
 531,
 546,
 550,
 553,
 564,
 579,
 587,
 593,
 605,
 612,
 613,
 626,
 626,
 639,
 643,
 647,
 671,
 672,
 676,
 710,
 713,
 718,
 720,
 722,
 730,
 771,
 777,
 779,
 780,
 780,
 786,
 792,
 793,
 799,
 807,
 823,
 833,
 852,
 871,
 871,
 883,
 893,
 909,
 915,
 918,
 922,
 925,
 937,
 938,
 939,
 940,
 972,
 973,
 976,
 989]



In [112]:

    
%time list_sort(random_list_maker(1000))









    



CPU times: user 68 ms, sys: 0 ns, total: 68 ms
Wall time: 88.6 ms






    Out[112]:





[0,
 0,
 1,
 2,
 3,
 3,
 3,
 3,
 8,
 11,
 12,
 12,
 13,
 14,
 14,
 14,
 14,
 17,
 17,
 18,
 19,
 20,
 20,
 21,
 21,
 23,
 23,
 23,
 25,
 25,
 27,
 27,
 28,
 29,
 30,
 30,
 31,
 32,
 33,
 33,
 37,
 37,
 37,
 38,
 38,
 40,
 41,
 43,
 43,
 44,
 45,
 46,
 47,
 51,
 53,
 54,
 55,
 58,
 60,
 60,
 60,
 60,
 61,
 63,
 63,
 64,
 65,
 67,
 67,
 69,
 70,
 70,
 71,
 71,
 73,
 73,
 73,
 74,
 74,
 74,
 74,
 74,
 75,
 75,
 75,
 76,
 76,
 78,
 78,
 80,
 80,
 80,
 81,
 83,
 85,
 90,
 91,
 91,
 92,
 92,
 92,
 95,
 95,
 95,
 97,
 97,
 98,
 99,
 99,
 99,
 101,
 101,
 102,
 102,
 103,
 104,
 105,
 106,
 106,
 107,
 107,
 107,
 108,
 108,
 109,
 109,
 111,
 112,
 113,
 114,
 116,
 117,
 118,
 118,
 118,
 119,
 120,
 120,
 120,
 121,
 121,
 121,
 121,
 123,
 125,
 127,
 128,
 128,
 129,
 132,
 133,
 134,
 134,
 137,
 137,
 137,
 139,
 139,
 140,
 140,
 141,
 142,
 144,
 144,
 145,
 145,
 147,
 151,
 152,
 152,
 152,
 154,
 156,
 159,
 160,
 160,
 161,
 161,
 161,
 165,
 165,
 166,
 167,
 168,
 168,
 168,
 172,
 172,
 173,
 173,
 175,
 177,
 177,
 177,
 179,
 181,
 181,
 183,
 183,
 184,
 187,
 187,
 187,
 187,
 188,
 190,
 192,
 192,
 193,
 194,
 196,
 198,
 199,
 199,
 201,
 202,
 202,
 203,
 203,
 203,
 204,
 204,
 206,
 206,
 207,
 208,
 208,
 209,
 210,
 211,
 211,
 211,
 213,
 216,
 216,
 217,
 217,
 219,
 220,
 220,
 220,
 220,
 220,
 221,
 223,
 224,
 227,
 230,
 232,
 232,
 233,
 234,
 235,
 236,
 237,
 239,
 240,
 242,
 242,
 243,
 243,
 244,
 245,
 246,
 246,
 246,
 247,
 248,
 248,
 248,
 250,
 252,
 252,
 253,
 256,
 257,
 259,
 259,
 259,
 260,
 260,
 262,
 262,
 263,
 264,
 265,
 267,
 268,
 269,
 269,
 270,
 270,
 271,
 274,
 276,
 276,
 276,
 278,
 278,
 279,
 279,
 279,
 280,
 280,
 281,
 282,
 282,
 283,
 284,
 287,
 288,
 288,
 289,
 290,
 291,
 293,
 293,
 293,
 294,
 294,
 294,
 294,
 296,
 297,
 298,
 298,
 298,
 299,
 300,
 301,
 301,
 302,
 302,
 303,
 304,
 304,
 305,
 306,
 307,
 308,
 309,
 313,
 314,
 316,
 317,
 321,
 321,
 322,
 322,
 323,
 324,
 325,
 325,
 326,
 327,
 327,
 328,
 328,
 329,
 329,
 329,
 330,
 330,
 332,
 332,
 333,
 333,
 335,
 335,
 335,
 336,
 336,
 338,
 340,
 344,
 344,
 345,
 347,
 348,
 349,
 349,
 349,
 349,
 350,
 350,
 351,
 351,
 352,
 353,
 353,
 354,
 355,
 358,
 363,
 364,
 365,
 366,
 367,
 368,
 368,
 369,
 372,
 373,
 373,
 375,
 375,
 376,
 376,
 378,
 379,
 380,
 381,
 387,
 387,
 387,
 388,
 389,
 390,
 391,
 392,
 393,
 394,
 394,
 395,
 396,
 397,
 398,
 401,
 402,
 403,
 403,
 403,
 404,
 404,
 404,
 405,
 409,
 410,
 411,
 414,
 415,
 415,
 416,
 416,
 416,
 418,
 421,
 421,
 422,
 422,
 423,
 423,
 423,
 423,
 423,
 424,
 425,
 425,
 430,
 431,
 431,
 431,
 433,
 433,
 433,
 437,
 439,
 439,
 439,
 439,
 440,
 441,
 441,
 442,
 443,
 446,
 449,
 449,
 451,
 452,
 452,
 452,
 453,
 453,
 453,
 454,
 454,
 454,
 457,
 457,
 458,
 458,
 460,
 461,
 462,
 463,
 463,
 468,
 469,
 469,
 470,
 470,
 470,
 471,
 471,
 471,
 473,
 474,
 475,
 476,
 477,
 477,
 478,
 479,
 480,
 480,
 481,
 481,
 482,
 482,
 482,
 483,
 484,
 485,
 487,
 490,
 492,
 492,
 493,
 496,
 499,
 499,
 499,
 504,
 506,
 506,
 508,
 510,
 510,
 512,
 512,
 512,
 513,
 514,
 515,
 517,
 518,
 519,
 521,
 522,
 522,
 523,
 523,
 524,
 526,
 528,
 531,
 532,
 535,
 535,
 535,
 537,
 539,
 541,
 541,
 542,
 543,
 543,
 545,
 548,
 550,
 552,
 554,
 555,
 555,
 558,
 561,
 563,
 565,
 566,
 566,
 569,
 570,
 574,
 575,
 576,
 576,
 577,
 577,
 578,
 578,
 578,
 578,
 579,
 580,
 582,
 583,
 583,
 584,
 590,
 590,
 593,
 593,
 593,
 594,
 598,
 602,
 604,
 604,
 605,
 607,
 610,
 612,
 615,
 616,
 616,
 616,
 617,
 617,
 618,
 619,
 623,
 623,
 623,
 625,
 627,
 627,
 630,
 638,
 638,
 639,
 642,
 644,
 645,
 645,
 647,
 648,
 648,
 648,
 649,
 651,
 651,
 652,
 652,
 653,
 653,
 655,
 655,
 656,
 656,
 657,
 658,
 659,
 660,
 661,
 661,
 663,
 664,
 664,
 665,
 667,
 670,
 671,
 671,
 672,
 672,
 672,
 672,
 673,
 674,
 675,
 675,
 676,
 677,
 678,
 679,
 679,
 680,
 680,
 680,
 680,
 681,
 682,
 685,
 686,
 691,
 691,
 692,
 693,
 694,
 695,
 695,
 698,
 699,
 699,
 700,
 702,
 702,
 703,
 703,
 704,
 705,
 705,
 705,
 706,
 706,
 706,
 707,
 707,
 709,
 713,
 714,
 714,
 715,
 715,
 715,
 716,
 716,
 716,
 718,
 720,
 720,
 722,
 723,
 723,
 723,
 725,
 726,
 726,
 727,
 728,
 728,
 728,
 728,
 730,
 730,
 730,
 731,
 732,
 735,
 738,
 739,
 740,
 740,
 744,
 744,
 745,
 746,
 746,
 748,
 750,
 750,
 751,
 752,
 753,
 753,
 754,
 755,
 756,
 756,
 757,
 758,
 760,
 760,
 760,
 763,
 767,
 768,
 768,
 770,
 770,
 771,
 773,
 778,
 778,
 779,
 780,
 780,
 781,
 782,
 784,
 784,
 785,
 786,
 787,
 790,
 791,
 793,
 793,
 793,
 793,
 796,
 796,
 797,
 797,
 798,
 799,
 799,
 800,
 800,
 800,
 803,
 803,
 803,
 805,
 805,
 805,
 806,
 807,
 808,
 808,
 808,
 810,
 810,
 812,
 813,
 814,
 814,
 815,
 815,
 819,
 820,
 820,
 820,
 820,
 821,
 822,
 823,
 826,
 827,
 827,
 829,
 831,
 832,
 833,
 834,
 835,
 835,
 838,
 838,
 838,
 841,
 842,
 843,
 843,
 844,
 844,
 845,
 846,
 846,
 847,
 850,
 850,
 852,
 853,
 854,
 856,
 858,
 861,
 862,
 862,
 863,
 865,
 865,
 866,
 866,
 871,
 873,
 873,
 873,
 874,
 876,
 878,
 879,
 880,
 881,
 882,
 882,
 882,
 883,
 883,
 884,
 884,
 885,
 885,
 890,
 891,
 892,
 892,
 892,
 894,
 894,
 896,
 896,
 896,
 898,
 898,
 899,
 901,
 901,
 901,
 902,
 905,
 908,
 908,
 909,
 909,
 910,
 913,
 914,
 914,
 915,
 918,
 918,
 919,
 919,
 920,
 921,
 922,
 923,
 923,
 923,
 924,
 925,
 925,
 926,
 928,
 931,
 931,
 932,
 933,
 934,
 935,
 936,
 938,
 940,
 942,
 943,
 943,
 944,
 945,
 945,
 946,
 948,
 949,
 949,
 950,
 951,
 951,
 953,
 953,
 955,
 955,
 955,
 956,
 958,
 959,
 961,
 962,
 962,
 964,
 965,
 965,
 966,
 967,
 968,
 970,
 970,
 970,
 972,
 976,
 978,
 978,
 979,
 979,
 980,
 981,
 983,
 983,
 983,
 984,
 984,
 984,
 984,
 985,
 987,
 987,
 987,
 987,
 989,
 991,
 992,
 993,
 994,
 994,
 995,
 996,
 996,
 997,
 998]



In [ ]: