merge_sort.py

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1


# Example usage:
data = [
    416,
    78,
    530,
    75,
    197,
    94,
    768,
    384,
    396,
    665,
    160,
    871,
    508,
    11,
    693,
    161,
    935,
    940,
    155,
    662,
    593,
    604,
    769,
    617,
    998,
    681,
    770,
    588,
    864,
    318,
    53,
    73,
    260,
    834,
    413,
    850,
    555,
    903,
    147,
    190,
    39,
    985,
    7,
    692,
    594,
    106,
    557,
    792,
    524,
    789,
    734,
    750,
    849,
    610,
    305,
    244,
    559,
    709,
    356,
    471,
    43,
    858,
    131,
    656,
    181,
    55,
    779,
    805,
    329,
    92,
    345,
    795,
    917,
    354,
    325,
    793,
    588,
    989,
    95,
    672,
    319,
    420,
    893,
    793,
    237,
    562,
    773,
    796,
    342,
    256,
    464,
    1000,
    500,
    706,
    589,
    379,
    627,
    655,
    956,
    378,
    302,
    870,
    591,
    371,
    728,
    411,
    907,
    206,
    673,
    365,
    425,
    49,
    820,
    477,
    390,
    933,
    920,
    49,
    246,
    930,
    145,
    320,
    34,
    925,
    222,
    595,
    63,
    698,
    965,
    125,
    436,
    542,
    274,
    594,
    721,
    47,
    728,
    625,
    629,
    455,
    272,
    966,
    71,
    182,
    685,
    535,
    867,
    790,
    977,
    189,
    425,
    213,
    397,
    120,
    961,
    943,
    538,
    497,
    582,
    1000,
    828,
    184,
    461,
    334,
    620,
    419,
    907,
    782,
    59,
    728,
    716,
    197,
    995,
    803,
    514,
    703,
    754,
    91,
    254,
    103,
    280,
    821,
    354,
    420,
    608,
    566,
    307,
    855,
    935,
    420,
    444,
    207,
    245,
    279,
    818,
    321,
    865,
    532,
    156,
    444,
    493,
    636,
    556,
    756,
    361,
    232,
    775,
    612,
    778,
    389,
    334,
    120,
    324,
    354,
    964,
    893,
    54,
    825,
    73,
    946,
    119,
    45,
    389,
    913,
    17,
    169,
    812,
    990,
    504,
    210,
    902,
    822,
    293,
    578,
    494,
    787,
    632,
    247,
    463,
    117,
    550,
    502,
    297,
    877,
    618,
    406,
    904,
    210,
    143,
    839,
    562,
    346,
    256,
    576,
    967,
    729,
    500,
    623,
    599,
    451,
    109,
    379,
    278,
    489,
    165,
    85,
    796,
    83,
    8,
    497,
    94,
    874,
    712,
    909,
    606,
    759,
    713,
    96,
    208,
    174,
    903,
    467,
    421,
    16,
    1000,
    83,
    589,
    170,
    125,
    684,
    302,
    529,
    356,
    290,
    686,
    854,
    457,
    219,
    806,
    88,
    456,
    910,
    376,
    27,
    126,
    946,
    434,
    403,
    152,
    861,
    276,
    580,
    694,
    69,
    517,
    296,
    199,
    115,
    244,
    653,
    491,
    365,
    958,
    623,
    292,
    486,
    434,
    862,
    40,
    681,
    854,
    767,
    927,
    956,
    929,
    368,
    121,
    437,
    75,
    230,
    640,
    471,
    915,
    391,
    828,
    484,
    766,
    285,
    648,
    145,
    427,
    848,
    127,
    281,
    677,
    5,
    99,
    602,
    504,
    922,
    754,
    578,
    660,
    637,
    930,
    5,
    299,
    217,
    681,
    336,
    639,
    897,
    993,
    747,
    536,
    102,
    815,
    773,
    617,
    127,
    583,
    935,
    878,
    761,
    630,
    629,
    300,
    996,
    88,
    538,
    669,
    800,
    70,
    791,
    217,
    472,
    615,
    542,
    33,
    521,
    710,
    509,
    590,
    220,
    117,
    924,
    413,
    199,
    792,
    865,
    207,
    363,
    339,
    954,
    812,
    131,
    1,
    302,
    291,
    727,
    496,
    979,
    421,
    294,
    106,
    653,
    952,
    622,
    162,
    47,
    17,
    999,
    711,
    29,
    202,
    975,
    520,
    622,
    207,
    366,
    788,
    756,
    349,
    510,
    61,
    1,
    616,
    68,
    186,
    232,
    300,
    994,
    760,
    544,
    529,
    290,
    542,
    792,
    936,
    51,
    773,
    223,
    672,
    925,
    398,
    583,
    740,
    2,
    64,
    426,
    373,
    387,
    154,
    6,
    684,
    254,
    426,
    511,
    664,
    747,
    144,
    921,
    949,
    865,
    71,
    755,
    356,
    635,
    327,
    273,
    128,
    390,
    188,
    256,
    305,
    206,
    136,
    253,
    355,
    290,
    402,
    128,
    500,
    324,
    946,
    969,
    828,
    124,
    57,
    607,
    78,
    629,
    30,
    944,
    520,
    891,
    151,
    191,
    995,
    659,
    710,
    615,
    275,
    222,
    370,
    886,
    437,
    471,
    5,
    687,
    674,
    464,
    672,
    138,
    875,
    24,
    14,
    783,
    267,
    753,
    839,
    191,
    736,
    962,
    570,
    918,
    75,
    825,
    353,
    126,
    922,
    422,
    96,
    21,
    90,
    780,
    962,
    998,
    722,
    951,
    86,
    156,
    897,
    587,
    853,
    774,
    525,
    546,
    863,
    706,
    768,
    468,
    371,
    852,
    329,
    356,
    733,
    775,
    232,
    556,
    460,
    229,
    608,
    362,
    242,
    882,
    117,
    859,
    15,
    447,
    61,
    152,
    892,
    563,
    123,
    180,
    980,
    309,
    136,
    271,
    218,
    636,
    500,
    897,
    51,
    262,
    254,
    73,
    944,
    981,
    243,
    810,
    390,
    420,
    844,
    275,
    299,
    277,
    706,
    111,
    649,
    555,
    179,
    840,
    899,
    416,
    22,
    259,
    123,
    945,
    668,
    646,
    740,
    748,
    459,
    22,
    96,
    270,
    637,
    598,
    537,
    526,
    331,
    437,
    4,
    592,
    274,
    182,
    669,
    246,
    39,
    841,
    953,
    522,
    467,
    753,
    246,
    459,
    514,
    408,
    393,
    197,
    538,
    180,
    361,
    982,
    295,
    555,
    113,
    187,
    247,
    134,
    280,
    291,
    506,
    277,
    710,
    802,
    176,
    79,
    855,
    981,
    462,
    43,
    999,
    594,
    985,
    226,
    89,
    869,
    416,
    166,
    608,
    500,
    240,
    456,
    103,
    396,
    764,
    172,
    382,
    914,
    26,
    893,
    482,
    995,
    468,
    128,
    176,
    799,
    894,
    421,
    464,
    591,
    435,
    294,
    23,
    847,
    388,
    76,
    746,
    515,
    419,
    445,
    268,
    773,
    237,
    194,
    571,
    111,
    134,
    981,
    42,
    472,
    728,
    206,
    13,
    242,
    559,
    153,
    916,
    749,
    34,
    292,
    620,
    86,
    720,
    285,
    467,
    75,
    510,
    730,
    131,
    891,
    425,
    137,
    343,
    873,
    694,
    57,
    172,
    700,
    837,
    136,
    613,
    895,
    501,
    209,
    998,
    111,
    389,
    18,
    288,
    731,
    234,
    74,
    350,
    770,
    368,
    646,
    915,
    774,
    1000,
    220,
    8,
    168,
    443,
    497,
    48,
    254,
    380,
    259,
    370,
    575,
    142,
    365,
    932,
    635,
    354,
    568,
    934,
    198,
    447,
    473,
    899,
    56,
    536,
    103,
    630,
    593,
    790,
    662,
    878,
    719,
    421,
    676,
    754,
    268,
    137,
    95,
    653,
    332,
    526,
    364,
    158,
    319,
    392,
    188,
    457,
    84,
    171,
    711,
    133,
    603,
    281,
    196,
    593,
    996,
    38,
    34,
    579,
    755,
    606,
    532,
    844,
    642,
    264,
    534,
    460,
    800,
    616,
    800,
    386,
    74,
    49,
    734,
    755,
    806,
    516,
    827,
    686,
    717,
    925,
    853,
    748,
    53,
    556,
    819,
    696,
    306,
    461,
    792,
    668,
    261,
    662,
    453,
    568,
    187,
    168,
    335,
    474,
    695,
    567,
    357,
    365,
    492,
    112,
    937,
    883,
    294,
    219,
    472,
    525,
    835,
    203,
    345,
    381,
    844,
    496,
    56,
    200,
    528,
    128,
    502,
    367,
    752,
    197,
    990,
    419,
    136,
    675,
    997,
    955,
    12,
    532,
    344,
    146,
    493,
    691,
    801,
    886,
    237,
    654,
    173,
    548,
    316,
    160,
    548,
    335,
    549,
    46,
    446,
    165,
    683,
    206,
    484,
    553,
    852,
    719,
    485,
    238,
    583,
    559,
    706,
    312,
    779,
    77,
    73,
    116,
    881,
    349,
    911,
    53,
    985,
    210,
    594,
    932,
    239,
    346,
    50,
    569,
    826,
    617,
    578,
    171,
    761,
    873,
    118,
    315,
    445,
    253,
    421,
    377,
    649,
    251,
    88,
    687,
    571,
    945,
    244,
    405,
    954,
    228,
    254,
    953,
    167,
    428,
    58,
    617,
    390,
    825,
    160,
    109,
    52,
    762,
    459,
    552,
    373,
    526,
    234,
]
merge_sort(data)
print("Merge Sorted Data:", data)