gistfile1.js

function mergesort(array) {

  console.log('Merge Sorting Array:');
  console.log(array);

  var working_arrays = [];
  var sorted_array = [];
  var final_length = array.length;
  var next_item;

  // push each item into an Array of Arrays, the working array
  while(array.length > 0) {
    next_item = array.pop();
    working_arrays.push([next_item]);
  }


  console.log("remaining: " + array.length)

  // now we have individual items like this:
  // [n], [n], [n], [n], [n], [n], [n], [n]
  // 
  // and we're going to iteratively make sorted arrays like this:
  // [n,n], [n,n], [n,n], [n,n]
  // 
  // then:
  // [n,n,n,n], [n,n,n,n]
  // 
  // and finally:
  // [n,n,n,n,n,n,n,n]
  // 

  var merged_array = [];

  // until the final, sorted array is of the expected length
  while(working_arrays.length > 0) {

    // pop sub-arrays of the working array
    var first_array = working_arrays.pop();
    var second_array = working_arrays.pop();

    // console.log('first array, length ' + first_array.length + ', items are : ' + first_array);
    // console.log('second array, length ' + second_array.length + ', items are : ' + second_array);

    while((first_array.length > 0) || (second_array.length > 0)) {

      // compare single items at a time, drawing inwards as we go
      var left_item = first_array[0];
      // console.log('left item: ' + left_item);
      var right_item = second_array[0];
      // console.log('right item: ' + right_item);

      // i prefer for clarity to handle these undefined states individually
      if (typeof left_item == 'undefined') {
        // console.log('pushing: ' + right_item);
        merged_array.push(second_array.shift());

      } else if (typeof right_item == 'undefined') {
        // console.log('pushing: ' + left_item);
        merged_array.push(first_array.shift());

      } else if (left_item < right_item) {
        // console.log('pushing: ' + left_item);
        merged_array.push(first_array.shift());

      } else {
        // console.log('pushing: ' + right_item);
        merged_array.push(second_array.shift());

      }

      // console.log('so far: '  + merged_array)
      // console.log("\n")

    }

    if (merged_array.length == final_length) {

    } else {
      working_arrays.unshift(merged_array);
      merged_array = [];
    }

  }

  return merged_array;
}

// start with an unsorted array
var array = [1687, 4274, 4883, 4051, 2685, 4552, 1610, 514, 3299, 1301, 2446, 968, 4401, 3672, 3404, 4154, 1803, 2374, 1976, 4510, 828, 1772, 1831, 1827, 2654, 338, 93, 3415, 3481, 3738, 1482, 2554, 3476, 4365, 4183, 931, 3606, 2211, 3615, 4350, 4484, 849, 2268, 3009, 666, 3048, 3346, 2524, 4897, 1146, 4182, 2571, 366, 541, 125, 1677, 3187, 1417, 2541, 4566, 1535, 2398, 1249, 1311, 2381, 3907, 3519, 4385, 2622, 660, 3448, 3579, 1269, 2800, 3412, 4174, 641, 747, 1770, 3678, 3367, 3693, 651, 2202, 4835, 1810, 3574, 1685, 4658, 1085, 4289, 2403, 391, 649, 2705, 1833, 4970, 905, 2053, 3476, 2309, 670, 1711, 605, 878, 964, 3460, 3488, 4095, 4292, 3093, 4009, 2025, 3233, 1114, 1068, 974, 3486, 2334, 396, 2485, 3258, 538, 3095, 1807, 2549, 838, 3579, 3814, 1539, 2985, 559, 4159, 4644, 2060, 1608, 4905, 48, 1477, 2848, 728, 4799, 4846, 29, 2595, 4423, 1704, 3276, 3131, 3986, 4298, 415, 3112, 2867, 2459, 4792, 3350, 529, 3579, 4297, 3691, 3245, 768, 2419, 2029, 2705, 4322, 3586, 3670, 1936, 2272, 2267, 1224, 271, 3785, 578, 2887, 1528, 1696, 676, 4360, 4801, 2740, 803, 685, 1318, 2849, 71, 4934, 1404, 323, 3747, 1127, 40, 2469, 922, 779, 1885, 4993, 586, 1228, 588, 3460, 1571, 4507, 1853, 1422, 2458, 4730, 143, 1850, 3324, 3049, 2590, 1833, 106, 267, 801, 534, 3824, 3242, 351, 1395, 2748, 1327, 1635, 2397, 2184, 1256, 4258, 1503, 432, 2459, 2912, 1634, 690, 2077, 2405, 4072, 1680, 1486, 2808, 2706, 2157, 4301, 4107, 1552, 1171, 1276, 2390, 932, 3473, 850, 161, 3081, 1255, 1047, 3704, 1158, 2494, 1432, 4187, 3085, 473, 631, 230, 837, 2808, 4210, 1058, 1493, 503, 1202, 79, 4744, 4853, 668, 2337, 4100, 1989, 3923, 3061, 1153, 1831, 1540, 3976, 3327, 1374, 3046, 1252, 2798, 599, 2767, 3158, 4071, 4238, 2365, 25, 883, 4295, 369, 2494, 4141, 45, 1498, 1277, 2831, 2941, 414, 460, 1045, 4847, 3136, 2994, 2005, 4445, 144, 2959, 213, 1426, 4211, 2799, 3624, 2289, 2297, 2660, 3233, 1745, 4118, 708, 2559, 3148, 2354, 4218, 3427, 1267, 4054, 1391, 2310, 1678, 807, 2686, 2321, 3265, 3092, 1062, 1358, 990, 193, 2301, 3649, 4044, 2295, 2861, 1780, 1985, 541, 1300, 3937, 829, 3145, 2948, 2153, 2018, 2407, 1134, 3731, 724, 1370, 382, 3162, 191, 1808, 1618, 196, 4194, 197, 1338, 2358, 2873, 3479, 1989, 941, 2502, 1622, 2017, 980, 4064, 1031, 3351, 4530, 1306, 4705, 3694, 1839, 4488, 1262, 836, 299, 135, 923, 4957, 1640, 2436, 3489, 2482, 296, 3873, 3219, 3158, 2332, 4048, 3857, 219, 4154, 247, 4978, 2265, 3279, 59, 4205, 939, 3462, 4916, 2583, 1339, 1104, 1504, 337, 3933, 4100, 3309, 3076, 3178, 69, 1552, 1521, 835, 1557, 1254, 4312, 1501, 1376, 987, 3503, 3210, 28, 2601, 1323, 4779, 2247, 4112, 814, 1638, 1258, 3459, 4036, 979, 2160, 1123, 4668, 4124, 468, 4663, 469, 180, 1726, 725, 4996, 3309, 1535, 3966, 4020, 1535, 1288, 3268, 4675, 1913, 1127, 2410, 4342, 968, 447, 4235, 480, 3414, 1089, 475, 2849, 1185, 1013, 4100, 2952, 4088, 3620, 3328, 1891, 2781, 1035, 1855, 1498, 1903, 955, 2214, 354, 3822, 1685, 4083, 4380, 1885, 1172, 210, 3909, 59, 3948, 938, 4432, 693, 203, 4924, 1253, 868, 3248, 2701, 1349, 1788, 1896, 4559, 2390, 1469, 4445, 591, 4469, 744, 7, 3025, 1124, 2464, 3150, 694, 343, 220, 497, 1350, 803, 4426, 792, 1887, 3649, 3059, 73, 1313, 1073, 2827, 1339, 1577, 3570, 4257, 3591, 4175, 4183, 2869, 2298, 4409, 4891, 3712, 1861, 2211, 3042, 4007, 919, 2309, 257, 698, 3302, 502, 4827, 1236, 4938, 1885, 44, 2496, 2571, 4352, 3310, 3219, 4659, 1547, 4488, 1711, 13, 4024, 4689, 4564, 2694, 4152, 4211, 4784, 1342, 637, 3518, 3891, 725, 4713, 812, 4104, 3511, 4566, 2474, 1798, 0, 2039, 1200, 134, 835, 2326, 4887, 3874, 437, 3853, 2048, 4979, 4268, 2049, 2640, 4569, 4415, 1293, 475, 2991, 4900, 3552, 3661, 4140, 4602, 1624, 4433, 4608, 4665, 1328, 4125, 1786, 2032, 4200, 4417, 3556, 4367, 2511, 4986, 3453, 878, 4617, 3360, 169, 4053, 2642, 4020, 2132, 3587, 760, 2411, 1968, 529, 1389, 8, 1968, 2049, 1463, 1576, 2190, 652, 3291, 1040, 2118, 1790, 1627, 4731, 1625, 2460, 3162, 110, 2137, 1680, 2793, 509, 4217, 474, 719, 3578, 1014, 3056, 1247, 3052, 4536, 4279, 503, 308, 3919, 805, 1380, 814, 1949, 1020, 4596, 3098, 2498, 3091, 298, 2103, 2956, 1577, 2005, 685, 1145, 377, 3235, 1861, 2391, 2163, 3412, 4951, 2838, 3269, 3432, 1858, 2718, 3643, 7, 2962, 325, 1151, 2502, 2162, 851, 1206, 392, 3621, 1191, 4325, 288, 4309, 3626, 3639, 2573, 252, 1468, 158, 3984, 723, 127, 3359, 730, 185, 772, 206, 3964, 2024, 2047, 213, 3162, 1210, 471, 2013, 2530, 2178, 649, 1996, 4020, 4322, 982, 4891, 23, 4509, 3113, 3764, 260, 2075, 2501, 4553, 4759, 4554, 2030, 2239, 1161, 1270, 493, 659, 3002, 1383, 438, 2820, 4837, 136, 739, 4351, 4067, 3473, 2164, 1247, 160, 1517, 1544, 1539, 193, 2526, 158, 4405, 2749, 3569, 3390, 529, 3473, 4790, 129, 3236, 2809, 3247, 3822, 1249, 1067, 4944, 2515, 1661, 4124, 3740, 1977, 2429, 2891, 2477, 1416, 1239, 4246, 4672, 3985, 3131, 3577, 2930, 2639, 2533, 954, 430, 2483, 387, 3391, 786, 3359, 462, 2947, 1326, 2858, 4224, 4813, 1096, 4849, 845, 691, 2959, 3793, 64, 1367, 2623, 3660, 4964, 4242, 667, 1243, 3878, 4485, 441, 3620, 3397, 4457, 3172, 4624, 792, 2412, 4041, 3948, 3807, 2015, 4478, 4001, 2178, 4210, 4223, 780, 1518, 1225, 158, 3024, 1690, 1144, 3791, 3758, 3892, 4143, 3024, 1407, 4944, 4657, 747, 4802, 912, 4950, 364, 741, 3738, 4805, 4753, 2786, 1768, 3975, 2124, 760, 1368, 1952, 3700, 2134, 3906, 661, 2785, 3526, 4580, 1327, 4307, 1502, 1784, 50, 3557, 3093, 4912, 1753, 1215, 4617, 1768, 3584, 2643, 3722, 892, 887, 3057, 3276, 597, 1030, 4702, 2514, 2826, 4099, 2734, 1517, 1849, 3387, 1598, 1682, 860, 2007, 3192, 4830, 3752, 1326, 4570, 3471, 244, 3335, 3466, 4156, 3006, 4206, 2880, 592, 868, 3968, 2202, 2540, 1018, 3296, 3861, 3627, 4887, 3876, 4253, 4556, 2046, 1705, 4726, 3310, 1072, 2704, 3908, 561, 3439, 2127, 2204, 3923, 4451, 125, 331, 2479, 670, 2829, 332, 4758, 1134, 797, 4103, 1191, 3487, 3872, 1500, 2144, 2975, 3328, 3382, 4958, 2621, 1907, 1923, 722, 831, 1076, 269, 631, 800, 3693, 3531, 2473, 2967, 2624, 1861, 3052, 2386, 4477, 2390, 779, 1091, 1709, 3275, 4457, 535, 587, 1389, 4581, 4921, 1883, 400, 3433, 3655, 1047, 1554, 1746, 314, 4159, 2343, 1951, 4051, 3116, 3073, 1400, 3949, 2311, 47, 1470, 760, 286, 4202, 2038, 306, 2555, 2309, 4487, 275, 1844, 3635, 1981, 2590, 3429, 2909, 4207, 313, 202, 1318, 2916, 3609, 2464, 286, 2685, 3447, 2680, 1449, 3632, 2118, 715, 2641, 3352, 1634, 1273, 4250, 1262, 1736, 1172, 3723, 4138, 2601, 3538, 36, 1845, 1056, 3268, 3086, 1962, 4450, 488, 3361, 1227, 3794, 1435, 3364, 4845, 4929, 1813, 2199, 2116, 957, 305, 1803, 4390, 327, 3812, 2800, 1338, 4704, 1082, 4680, 1291, 1422, 49, 3260, 479, 3630, 955, 4964, 4419, 776, 2111, 3367, 4543, 4154, 2710, 1377, 630, 2170, 853, 321, 1865, 1451, 4656, 1533, 3391, 4844, 1261, 1255, 2163, 1884, 2667, 3726, 2035, 1114, 4415, 2741, 594, 293, 3551, 1803, 4247, 3944, 4256, 3464, 3838, 653, 1419, 1088, 888, 4318, 3465, 1086, 2782, 2295, 4218, 4499, 4193, 359, 4991, 3540, 2408, 1609, 3689, 2773, 4240, 295, 3567, 3647, 1680, 4756, 3699, 620, 844, 1724, 3965, 1573, 3843, 1853, 296, 2838, 1631, 1306, 1664, 3964, 3959, 2755, 568, 4014, 2648, 3259, 2976, 582, 3888, 4489, 2800, 778, 1420, 2387, 922, 4960, 2126, 2326, 542, 2705, 3462, 3302, 1294, 4154, 1990, 4184, 3967, 4350, 2988, 2299, 3815, 1119, 2518, 244, 831, 4128, 3190, 3654, 146, 4451, 4877, 4553, 327, 1335, 2847, 3236, 2663, 1335, 3197, 3660, 3979, 4261, 3519, 545, 3872, 2654, 4540, 4536, 4405, 1861, 3699, 4421, 3057, 4855, 2241, 3450, 3174, 455, 4774, 884, 3433, 4277, 621, 1310, 2398, 593, 1927, 515, 4794, 1885, 680, 1724, 3575, 911, 1268, 4760, 4101, 45, 4412, 3528, 2782, 2104, 3051, 2374, 4277, 1812, 2497, 2685, 2958, 1494, 1144, 2689, 48, 1791, 1200, 1757, 4073, 206, 4538, 364, 584, 2888, 1545, 4025, 3737, 3193, 59, 3616, 1062, 1064, 464, 2462, 4971, 2280, 4073, 530, 4332, 1801, 4434, 2359, 3331, 1468, 1738, 189, 4864, 3576, 4096, 2300, 2324, 2728, 1374, 2836, 800, 2334, 2196, 1397, 4571, 3694, 983, 3525, 2523, 3210, 2132, 151, 1809, 311, 4813, 2070, 1430, 3361, 2786, 1301, 966, 2057, 1496, 1475, 1046, 4797, 1333, 2935, 1226, 2154, 2461, 4074, 3705, 3866, 3990, 3926, 269, 154, 2628, 2336, 2484, 91, 2982, 4599, 1588, 3127, 4528, 435, 838, 2693, 3389, 1286, 4794, 2046, 735, 664, 2188, 3382, 4332, 28, 3093, 1862, 972, 1981, 1164, 4207, 2799, 1518, 4896, 1032, 1860, 1434, 2970, 1905, 521, 47, 4211, 3133, 2873, 3593, 1206, 2771, 1974, 4228, 1513, 2289, 1443, 3394, 604, 498, 4749, 74, 4820, 404, 1846, 503, 4402, 3038, 97, 3316, 1453, 4227, 2590, 644, 3718, 887, 4495, 695, 4303, 1024, 1176, 3050, 1879, 3479, 1227, 3661, 3586, 3787, 3565, 131, 1434, 2077, 2848, 495, 952, 557, 2368, 935, 3925, 3672, 2420, 2148, 4650, 1688, 4641, 2310, 90, 839, 496, 493, 3063, 732, 3091, 4228, 3325, 3016, 1779, 3702, 1511, 368, 2817, 3517, 4574, 3072, 2068, 4925, 23, 4522, 2149, 604, 4821, 577, 2740, 174, 2165, 4322, 3833, 776, 70, 3120, 3598, 3143, 1064, 3221, 3691, 3148, 3508, 2227, 3033, 2860, 4577, 2217, 3018, 882, 1306, 1639, 1415, 1439, 4631, 3237, 2941, 1825, 1940, 2026, 4649, 3436, 4397, 1737, 4090, 3960, 275, 3315, 2115, 1409, 2203, 3514, 2273, 873, 2212, 4889, 3397, 2688, 274, 3264, 1393, 2862, 2752, 2390, 2383, 4245, 1920, 2279, 3266, 3394, 4154, 950, 2992, 4244, 1160, 4954, 4036, 3118, 1656, 4579, 4327, 4267, 544, 1080, 2078, 3531, 3930, 594, 257, 112, 301, 3551, 3420, 4504, 2169, 1178, 3349, 3213, 3747, 1877, 3728, 789, 4941, 4967, 4319, 2217, 4949, 2922, 3861, 4960, 2911, 3510, 988, 4686, 3853, 2691, 4551, 1045, 3401, 902, 2212, 4934, 1902, 1054, 1690, 4914, 755, 934, 3661, 4385, 1859, 429, 2730, 3431, 1313, 4061, 333, 2496, 783, 2648, 202, 1765, 1400, 3933, 1446, 889, 860, 1487, 2877, 2292, 319, 4135, 2814, 4277, 1038, 4865, 1824, 3769, 1967, 3310, 3852, 115, 4175, 580, 1546, 1144, 4082, 3101, 4360, 959, 4715, 2649, 3094, 4869, 1955, 475, 3879, 2099, 4630, 3764, 624, 4445, 2244, 191, 4863, 4153, 4446, 4246, 1475, 3422, 3825, 1262, 971, 2461, 783, 372, 204, 1325, 3032, 3086, 3375, 2098, 202, 2025, 321, 3504, 1439, 3774, 1320, 2243, 3262, 1491, 3722, 1344, 2673, 4911, 2290, 1575, 2701, 766, 405, 4085, 167, 751, 4680, 3228, 1857, 1876, 1744, 4524, 1677, 3765, 2540, 2396, 3519, 1112, 3719, 4142, 1906, 1751, 2949, 638, 1077, 3967, 4817, 595, 1783, 3418, 4326, 2569, 989, 11, 2584, 41, 3783, 2904, 2025, 2323, 3019, 623, 4357, 135, 3078, 982, 3079, 3245, 185, 377, 1377, 2225, 40, 3052, 355, 795, 2455, 2098, 2141, 3632, 612, 3795, 3383, 1238, 978, 2154, 1550, 1195, 752, 826, 3442, 2004, 732, 3790, 3611, 1272, 2624, 3263, 940, 895, 3663, 237, 2249, 1115, 855, 1306, 356, 4648, 3474, 1681, 2399, 1812, 1462, 2724, 4120, 2687, 1100, 517, 3013, 731, 4383, 3883, 163, 4516, 811, 2208, 3139, 348, 2967, 3304, 3317, 1657, 3545, 3874, 3659, 3902, 2581, 80, 3627, 731, 1904, 1150, 2158, 480, 2860, 4084, 3321, 1941, 1224, 664, 3940, 3276, 2913, 1727, 3055, 933, 2780, 592, 4582, 2530, 2455, 3271, 213, 1600, 184, 517, 1312, 513, 4359, 954, 2496, 4967, 3609, 4904, 4558, 1623, 4564, 1491, 2818, 170, 1392, 3968, 2590, 4635, 2609, 2705, 3000, 77, 4170, 1956, 3233, 3583, 1757, 4601, 864, 3184, 2780, 3500, 1232, 784, 633, 3438, 3955, 2015, 2561, 4204, 3457, 3364, 1673, 3003, 870, 1363, 3337, 4589, 1597, 1991, 4172, 406, 3039, 1716, 1015, 626, 1279, 1133, 2832, 3230, 258, 4962, 300, 1552, 378, 3052, 1392, 3720, 3572, 1275, 2655, 3408, 302, 4133, 426, 2258, 2060, 1706, 1717, 1343, 3012, 228, 1969, 124, 4540, 4545, 3882, 3615, 4036, 1413, 76, 438, 2452, 1028, 3530, 2821, 249, 707, 823, 1508, 3602, 3371, 4775, 3348, 1301, 3401, 2519, 1864, 3744, 4295, 3896, 3699, 2568, 2769, 2413, 3486, 3201, 1475, 1243, 3949, 4194, 3700, 2409, 569, 4633, 4313, 2586, 3017, 4719, 4780, 3901, 1262, 4453, 527, 3466, 3681, 2073, 3165, 3898, 3193, 133, 4390, 1632, 3512, 162, 3230, 3386, 2213, 2546, 1721, 3932, 1928, 3068, 4073, 3381, 3599, 622, 3579, 4658, 3486, 1305, 4390, 2057, 2068, 3379, 1275, 3215, 3075, 1172, 3775, 660, 321, 2472, 4947, 4766, 2293, 2903, 589, 593, 4792, 4400, 4625, 4955, 2270, 804, 1350, 4527, 499, 995, 1354, 4576, 2954, 658, 3005, 2601, 3637, 4508, 2021, 538, 750, 2462, 458, 2661, 1521, 1570, 1700, 4121, 2233, 4895, 1324, 4416, 411, 202, 1064, 1895, 4580, 2088, 2076, 3793, 970, 1022, 670, 3459, 2632, 639, 4363, 3170, 4848, 3042, 1471, 4830, 4751, 4539, 447, 4066, 1482, 1376, 3210, 633, 4771, 526, 671, 1864, 3959, 4929, 2096, 3440, 1198, 898, 2349, 3666, 366, 1526, 4103, 3602, 3344, 958, 2550, 3861, 1125, 3304, 2759, 247, 3494, 3493, 2994, 1742, 840, 1537, 2267, 1842, 3448, 2381, 189, 3632, 459, 548, 3261, 3231, 3390, 4878, 2500, 750, 2393, 901, 1090, 2461, 3724, 2820, 1913, 1946, 2390, 2156, 2112, 3460, 1917, 2255, 4218, 1782, 1850, 1812, 586, 347, 3793, 1759, 3987, 2370, 2209, 2278, 2065, 664, 4690, 327, 396, 457, 930, 1101, 4889, 1791, 1051, 2162, 4207, 4614, 1625, 2995, 163, 1329, 2725, 3724, 853, 2331, 3002, 4511, 3870, 886, 2495, 3166, 4536, 3117, 789, 596, 4010, 4413, 3818, 3637, 2671, 4517, 1285, 474, 4847, 1493, 3610, 20, 1321, 1786, 4717, 667, 4053, 3804, 3337, 2016, 306, 2552, 4159, 1933, 2903, 4688, 758, 2349, 2995, 627, 4589, 4522, 15, 404, 1784, 1839, 2004, 4348, 3619, 2705, 925, 1572, 3021, 321, 4168, 2362, 3529, 1844, 134, 905, 654, 3858, 4313, 2602, 4166, 1948, 1322, 4960, 1765, 2485, 2, 2980, 242, 4434, 4860, 2301, 4522, 4372, 3376, 3339, 2331, 946, 4550, 240, 1110, 4382, 3905, 2254, 3410, 4971, 4819, 3616, 2857, 1819, 2174, 576, 2927, 3687, 4091, 1262, 1933, 4063, 3828, 4280, 1671, 369, 712, 1329, 4172, 768, 3770, 3781, 4638, 3598, 4210, 828, 1110, 1779, 2279, 722, 4, 2193, 4903, 3958, 3962, 3733, 3318, 2794, 514, 1290, 4221, 4179, 4306, 1032, 457, 2647, 1855, 610, 4733, 4094, 755, 1180, 2105, 757, 3353, 492, 3737, 1872, 1706, 1938, 4160, 3924, 1832, 2539, 1964, 4053, 3119, 44, 2920, 4097, 1889, 2923, 1305, 2103, 4285, 2201, 900, 3449, 608, 2414, 197, 1633, 1889, 4806, 789, 3193, 4971, 3350, 151, 323, 1036, 4951, 2638, 1780, 1929, 116, 920, 453, 4453, 1546, 4166, 3568, 464, 4367, 1243, 2863, 4579, 3438, 2323, 3953, 1740, 2585, 995, 2070, 3842, 2305, 4873, 2227, 4089, 2052, 103, 4591, 128, 1412, 4059, 1421, 327, 1673, 2479, 784, 2276, 251, 1611, 4240, 696, 478, 1508, 2765, 513, 768, 752, 4145, 2202, 3345, 3347, 734, 2651, 2851, 3272, 2242, 4117, 172, 2728, 1202, 4011, 537, 97, 2391, 1669, 2239, 2577, 638, 4101, 1715, 787, 324, 2729, 1728, 4293, 2863, 3108, 4236, 4315, 4305, 2552, 2189, 4511, 1731, 2169, 61, 2965, 1458, 2371, 2046, 567, 4841, 4081, 201, 174, 2866, 2727, 3606, 1670, 2843, 4013, 2743, 228, 2622, 4232, 315, 4710, 1969, 1652, 852, 3175, 2833, 2594, 3170, 425, 917, 3521, 3148, 3175, 2835, 2643, 108, 2989, 216, 2051, 526, 4155, 577, 3773, 3656, 1361, 4103, 1288, 378, 2623, 3912, 624, 421, 4306, 4440, 815, 4991, 2248, 2590, 197, 419, 424, 529, 4498, 1092, 2499, 895, 1968, 3000, 4381, 1270, 4461, 285, 2589, 1131, 3720, 3691, 1916, 2158, 3797, 1837, 1007, 1427, 617, 49, 2919, 3090, 3810, 2690, 2105, 3672, 1220, 1136, 3246, 1051, 4401, 1823, 678, 1328, 4702, 1293, 4511, 2507, 2775, 1454, 1701, 2078, 1198, 2058, 2723, 4802, 1925, 204, 4954, 4359, 3782, 2055, 1119, 2096, 1831, 4439, 2396, 4043, 3106, 1935, 2845, 4771, 2552, 352, 4823, 3191, 3158, 4778, 3248, 4891, 4730, 1378, 4333, 1947, 36, 1091, 288, 367, 126, 992, 3785, 744, 4054, 3258, 2081, 4488, 2817, 1199, 3655, 2865, 3745, 8, 4939, 4735, 288, 4897, 1337, 2056, 2639, 3226, 2897, 358, 1682, 1136, 1893, 2714, 4341, 472, 4000, 793, 3655, 3642, 2170, 2823, 299, 1361, 1103, 4478, 2928, 25, 4258, 4844, 421, 505, 4097, 4213, 2307, 3188, 3989, 3804, 1561, 2891, 1768, 204, 863, 989, 4823, 2099, 3365, 2549, 847, 1544, 590, 3202, 550, 3257, 80, 3038, 3884, 3713, 2419, 548, 1469, 3368, 2425, 4917, 4884, 3753, 2426, 2306, 4628, 3605, 27, 2482, 2435, 3629, 2826, 2309, 613, 1742, 937, 2529, 640, 4085, 3551, 3594, 2400, 2917, 1726, 4981, 2697, 3632, 4559, 1597, 978, 860, 3287, 691, 3227, 2752, 551, 902, 2147, 1245, 3927, 167, 1417, 4085, 4920, 805, 4207, 3040, 2657, 2459, 1383, 4816, 769, 892, 888, 4344, 3944, 1201, 4726, 1364, 1494, 566, 2833, 3302, 4238, 3459, 2936, 425, 3243, 1771, 2915, 3031, 4796, 4601, 2233, 1011, 4902, 4924, 434, 4736, 935, 2890, 1149, 2315, 3361, 4718, 3639, 4385, 1117, 1363, 1720, 3952, 1134, 1881, 1647, 3515, 108, 2344, 1289, 3608, 3343, 1036, 4947, 3139, 1001, 4746, 532, 3490, 3654, 2021, 2988, 285, 4756, 1706, 134, 1373, 4264, 3740, 2091, 2413, 2311, 4343, 3282, 3313, 3293, 3681, 570, 3477, 3424, 634, 3807, 4084, 2338, 3714, 3495, 2878, 4311, 4761, 2092, 1622, 4949, 3851, 2960, 2152, 1179, 4995, 3306, 2724, 1853, 1664, 1896, 2194, 4687, 2685, 314, 981, 2612, 527, 683, 2770, 4063, 4673, 4256, 1348, 1172, 2498, 687, 3644, 3813, 75, 4730, 4220, 3294, 3909, 2735, 4862, 974, 1181, 3328, 515, 817, 2013, 1557, 2202, 1883, 4634, 4299, 586, 480, 3790, 4572, 4904, 4866, 2221, 2754, 3788, 1362, 2639, 693, 1730, 4324, 451, 3413, 4164, 1868, 207, 2370, 1684, 2431, 3792, 1282, 761, 4830, 1936, 965, 1091, 330, 4644, 4535, 2710, 303, 4051, 562, 2274, 521, 1290, 3354, 697, 3712, 4049, 3315, 1215, 1692, 903, 3120, 4063, 1725, 4588, 725, 2597, 3787, 4816, 3282, 421, 2035, 2029, 4116, 2622, 4621, 4826, 2212, 4974, 4910, 334, 2875, 615, 3588, 3974, 3684, 1096, 3841, 175, 1258, 4981, 2938, 394, 3386, 2277, 2916, 2305, 4123, 1723, 1826, 4083, 2348, 2427, 3185, 2574, 428, 4511, 2323, 4851, 4593, 3741, 4873, 1443, 1579, 3141, 237, 1002, 546, 349, 2168, 1289, 4785, 3068, 3133, 789, 1307, 4559, 4421, 3920, 2742, 4175, 3681, 3970, 4701, 216, 4603, 4307, 3393, 34, 3755, 3255, 632, 3255, 4380, 1360, 3982, 2242, 2845, 2664, 3255, 3605, 2195, 838, 3492, 1656, 3087, 3875, 3256, 1273, 2065, 3724, 4077, 784, 441, 3921, 3424, 4277, 1407, 3907, 4942, 1425, 516, 2503, 330, 4069, 1251, 2191, 4227, 165, 1335, 403, 3666, 3403, 443, 2052, 4566, 2951, 2132, 3009, 1769, 1007, 1885, 3670, 4806, 2406, 4713, 3728, 782, 4195, 4621, 1140, 4937, 4222, 4696, 1405, 4103, 4244, 2, 1397, 1726, 2243, 4739, 2657, 3656, 926, 3664, 2825, 4228, 4234, 1301, 29, 3201, 648, 2510, 4210, 274, 3829, 2080, 4340, 3661, 1384, 2312, 1800, 336, 715, 1357, 1832, 4316, 4091, 2250, 845, 3, 2124, 3450, 2185, 2626, 692, 739, 1381, 3065, 1988, 2416, 3830, 1611, 3887, 526, 1888, 1443, 2789, 3107, 1786, 836, 25, 1903, 266, 539, 3091, 3787, 3039, 1784, 4935, 1331, 2115, 2183, 1228, 474, 4110, 3434, 1453, 3141, 2245, 2694, 1240, 2594, 4222, 4877, 2606, 1133, 987, 1297, 4372, 4206, 1559, 1445, 2141, 3742, 4273, 1548, 912, 4438, 1366, 104, 1274, 4866, 242, 2170, 475, 708, 1074, 2514, 3250, 2921, 3860, 1303, 3778, 2316, 4557, 219, 4976, 4954, 864, 2041, 3856, 809, 3109, 504, 823, 1594, 1223, 2866, 4909, 118, 1868, 4811, 3093, 2373, 2143, 3314, 658, 113, 4692, 3827, 1756, 4566, 2300, 1782, 2050, 544, 662, 2329, 4645, 4848, 2935, 988, 1380, 4712, 4192, 2874, 1493, 2707, 1727, 3340, 156, 192, 1968, 2041, 822, 3058, 1784, 1098, 4469, 4777, 4482, 319, 480, 3045, 2932, 3535, 2123, 4796, 4018, 233, 4343, 3583, 3763, 1277, 3778, 313, 750, 3211, 4598, 1715, 2002, 1363, 4637, 4025, 761, 221, 4650, 3472, 726, 336, 4674, 3303, 487, 3404, 1022, 922, 1474, 3795, 6, 4345, 1199, 596, 2206, 307, 4823, 1437, 1480, 2480, 3736, 4160, 1480, 4942, 567, 3495, 4723, 201, 583, 586, 3725, 4496, 2971, 4018, 4937, 945, 2463, 3888, 1221, 271, 4225, 765, 653, 3926, 2463, 4791, 1873, 474, 1293, 514, 4123, 3093, 467, 2245, 4012, 3729, 4177, 2785, 1820, 4875, 1558, 3084, 2143, 2520, 465, 1095, 327, 1704, 4204, 4510, 3733, 4034, 3264, 3106, 4132, 1194, 3116, 4255, 4478, 294, 1542, 2933, 2446, 182, 1496, 654, 710, 4603, 2549, 3680, 3565, 4686, 2753, 3102, 389, 1694, 2226, 4394, 1359, 2856, 1588, 3648, 3356, 349, 3929, 1467, 2849, 1968, 2315, 431, 4209, 4674, 2889, 128, 3249, 413, 4163, 1002, 4216, 108, 3105, 2259, 3718, 216, 1939, 1985, 3468, 3674, 709, 1487, 1137, 4855, 884, 168, 3877, 2162, 155, 2668, 1996, 3362, 1528, 4747, 125, 721, 4786, 1720, 3944, 969, 4519, 4168, 3519, 12, 4181, 2015, 3698, 1628, 4253, 4535, 3080, 4997, 4284, 2090, 4278, 4872, 1610, 864, 2080, 773, 390, 4452, 3246, 651, 4297, 2362, 3508, 1961, 3218, 1064, 1548, 4548, 1903, 1763, 1540, 121, 2589, 4344, 960, 1420, 3688, 1471, 3205, 892, 4976, 2346, 3996, 4228, 3463, 3774, 627, 22, 1766, 1637, 786, 2842, 1033, 551, 4216, 3813, 3019, 4228, 3589, 2052, 3598, 1634, 4217, 1555, 376, 1834, 1040, 4272, 963, 3251, 2943, 1710, 4681, 3015, 1730, 4195, 195, 916, 1187, 2065, 281, 4953, 1334, 4561, 2401, 3083, 4075, 1239, 2116, 904, 4413, 366, 2173, 3551, 2169, 2584, 4859, 3177, 1183, 101, 461, 4934, 2705, 1491, 4682, 2899, 1829, 902, 605, 133, 4767, 4069, 853, 2691, 1486, 2040, 4080, 951, 2690, 3742, 68, 4086, 105, 3689, 64, 3114, 2361, 178, 3158, 2476, 70, 2185, 1795, 1687, 2192, 4484, 4609, 4076, 1524, 2938, 4336, 1634, 2616, 4451, 1560, 487, 121, 2220, 3315, 3554, 3846, 2567, 2760, 2009, 4563, 3208, 4797, 121, 864, 1503, 3904, 205, 1961, 890, 667, 25, 4810, 1772, 403, 4433, 466, 4216, 2230, 4413, 1465, 3457, 2127, 3380, 2435, 1866, 2081, 4290, 3330, 943, 1646, 2803, 4669, 4410, 1349, 935, 3263, 2708, 1454, 1573, 660, 1661, 4872, 2045, 3520, 1981, 1476, 4728, 1883, 4526, 3443, 1847, 4852, 3138, 2071, 2198, 2212, 1788, 1002, 712, 2364, 2661, 2753, 3705, 4666, 2441, 1129, 2621, 979, 1139, 1910, 1312, 3974, 102, 3431, 1434, 2850, 4485, 2611, 243, 4873, 2396, 2433, 2068, 2912, 1724, 3183, 1410, 2428, 2521, 1266, 3413, 2113, 1735, 399, 4216, 2959, 3390, 483, 1307, 3696, 2779, 501, 3596, 1117, 3347, 3222, 3120, 2212, 1357, 1780, 724, 1279, 611, 1824, 411, 1396, 888, 437, 974, 3262, 4068, 4888, 2666, 1145, 1891, 488, 3775, 2796, 1852, 4160, 1655, 1873, 3937, 2912, 2967, 4678, 1056, 564, 2211, 1657, 192, 1005, 2033, 2200, 608, 474, 1793, 1297, 411, 816, 1023, 385, 1252, 942, 3400, 2575, 3467, 4756, 4941, 90, 3919, 2325, 2196, 2705, 202, 688, 521, 2229, 4895, 3169, 1178, 123, 1475, 1971, 1997, 282, 3851, 3477, 3542, 1778, 2787, 682, 2627, 4452, 61, 2164, 3889, 4102, 1586, 3658, 351, 1547, 4176, 1142, 1708, 2254, 2646, 4750, 1486, 1959, 99, 64, 2164, 4785, 185, 3510, 3048, 4141, 1659, 11, 1979, 4852, 219, 2543, 1049, 3879, 1363, 2839, 4534, 3016, 4389, 2553, 4699, 2829, 3319, 700, 340, 2903, 2763, 1781, 4330, 52, 3873, 815, 3296, 1109, 3182, 4441, 3151, 3934, 1182, 4987, 1259, 906, 1505, 418, 4182, 3632, 2386, 756, 3641, 3661, 4134, 30, 396, 4002, 2370, 4082, 3207, 3056, 1698, 4150, 4104, 3146, 4699, 4908, 1138, 195, 3090, 3338, 603, 3956, 2863, 3365, 4695, 1395, 4647, 1690, 1139, 2795, 3679, 3195, 4153, 2641, 3705, 937, 2036, 3756, 1305, 1735, 156, 1597, 3701, 2005, 396, 1347, 1604, 3365, 4376, 2347, 2495, 3906, 611, 3456, 1433, 46, 3315, 3120, 3966, 123, 4672, 350, 4923, 908, 4427, 1886, 4691, 4292, 1086, 3335, 1933, 3925, 685, 586, 1968, 3961, 4910, 1339, 2220, 3536, 545, 2099, 775, 4332, 4640, 3254, 508, 1880, 2095, 3847, 1083, 4818, 698, 3325, 393, 1482, 2236, 3651, 801, 3325, 4104, 4354, 4305, 2908, 2989, 1380, 362, 374, 1699, 3604, 3499, 3549, 738, 2162, 2221, 584, 3711, 1251, 1403, 689, 2675, 553, 2454, 2438, 4287, 178, 3421, 2270, 2307, 3815, 3911, 795, 822, 238, 1301, 1476, 255, 2496, 4612, 4579, 2477, 1342, 835, 186, 1694, 3569, 947, 4155, 1642, 1667, 2742, 4752, 4056, 4082, 2506, 3753, 1545, 4466, 3178, 2002, 1746, 2402, 2765, 4221, 419, 2815, 4330, 2413, 2073, 2379, 1717, 892, 723, 4255, 3158, 3376, 406, 2359, 301, 2925, 3579, 2603, 947, 2711, 3219, 1779, 4904, 2554, 3696, 4247, 1604, 2699, 2824, 4993, 1848, 4469, 4873, 271, 1937, 1315, 3743, 2012, 458, 377, 1295, 1389, 88, 1085, 1996, 3208, 349, 1810, 498, 4701, 1348, 2071, 1079, 1539, 3188, 2341, 2813, 1731, 4556, 4626, 1193, 2509, 2252, 264, 3717, 4956, 617, 805, 852, 667, 3421, 4126, 3327, 3377, 1377, 3940, 1065, 1135, 123, 2509, 1051, 2123, 1443, 3288, 4856, 2268, 1908, 2891, 727, 4378, 2375, 4542, 602, 436, 2866, 2384, 4509, 2638, 4431, 4703, 117, 614, 152, 3221, 1193, 4028, 1010, 4493, 3454, 3977, 1938, 3594, 471, 3871, 428, 4410, 897, 4801, 4872, 571, 4488, 1843, 4784, 986, 1217, 1459, 2975, 2783, 2985, 4343, 2081, 4580, 225, 4640, 3062, 3168, 1316, 4051, 1374, 3351, 1558, 1608, 559, 3135, 1832, 316, 1173, 2881, 164, 2034, 2803, 4074, 4494, 650, 3074, 3981, 3601, 2790, 3476, 4065, 8, 685, 613, 911, 2738, 1084, 1781, 2143, 1522, 4179, 522, 4582, 1068, 3357, 110, 3907, 4784, 4325, 2016, 4066, 4089, 2031, 55, 75, 4091, 542, 3752, 1251, 4459, 1062, 1425, 424, 1989, 438, 2064, 2687, 4145, 1334, 762, 2761, 900, 4201, 2538, 4069, 401, 1588, 2386, 2705, 2617, 2335, 4208, 2863, 4937, 3697, 3223, 1649, 1908, 1762, 431, 2706, 188, 1270, 3800, 2437, 2082, 2279, 4229, 18, 3515, 3001, 4691, 4823, 4315, 2143, 3404, 3138, 2025, 2131, 2268, 316, 4032, 942, 874, 554, 3333, 3939, 277, 1545, 3592, 4983, 4132, 2703, 4014, 3595, 4322, 485, 4321, 4909, 671, 121, 3833, 2429, 1838, 852, 3217, 2758, 3537, 3406, 3348, 366, 2185, 170, 4985, 4059, 2141, 2164, 843, 3212, 764, 4334, 1281, 458, 3427, 915, 753, 2340, 1325, 2674, 3948, 105, 3954, 167, 4270, 3735, 3096, 3418, 4684, 3522, 3565, 3626, 4550, 3257, 1538, 3962, 3565, 3270, 1174, 4695, 3416, 957, 2996, 2869, 2821, 1971, 1112, 86, 410, 738, 2105, 4668, 362, 1592, 3569, 170, 774, 550, 4805, 2760, 1817, 1631, 1633, 3457, 4039, 3591, 1435, 3833, 2543, 301, 1389, 1743, 2902, 3087, 189, 1925, 4459, 3302, 485, 4160, 805, 1807, 202, 308, 317, 295, 2835, 249, 458, 3096, 2446, 2237, 1380, 2513, 4214, 965, 1697, 651, 3192, 51, 2844, 1197, 1146, 356, 4602, 2545, 501, 2500, 3569, 2689, 3258, 4665, 498, 3263, 3742, 1560, 698, 3015, 4934, 266, 624, 871, 1600, 1981, 4886, 3329, 408, 2018, 2751, 1054, 648, 1937, 1370, 840, 3930, 3830, 1299, 1948, 928, 3456, 2382, 880, 688, 99, 438, 945, 206, 3296, 1750, 2811, 2526, 3416, 1838, 3273, 77, 470, 980, 4116, 3274, 998, 1322, 2130, 4778, 3192, 662, 100, 4933, 1729, 47, 4504, 2968, 4667, 3056, 4394, 2118, 3633, 2494, 4124, 4346, 1897, 481, 3743, 466, 2208, 4674, 3257, 4976, 4556, 906, 3234, 954, 4349, 97, 526, 1695, 1175, 4132, 4051, 2357, 1344, 3743, 3644, 705, 3503, 479, 4584, 771, 1339, 389, 946, 558, 1889, 2407, 724, 3885, 2187, 4334, 3160, 2100, 2992, 4517, 3080, 153, 711, 659, 2005, 1804, 3581, 1379, 2938, 2559, 4882, 4185, 247, 4702, 2479, 427, 2644, 1142, 2800, 3592, 434, 4652, 3333, 3133, 165, 561, 4954, 1354, 4665, 3346, 4987, 4244, 1391, 774, 485, 3202, 1760, 4013, 1581, 3851, 1535, 2551, 3531, 1033, 366, 2985, 3284, 1294, 298, 3785, 1534, 3770, 4612, 3362, 724, 1339, 849, 4651, 2322, 2622, 2006, 1885, 949, 2191, 4245, 4863, 3966, 4167, 3596, 202, 3700, 4601, 4433, 1811, 4450, 96, 491, 3276, 3890, 3740, 3493, 4916, 3118, 1220, 3871, 4498, 426, 972, 622, 2205, 70, 1970, 2151, 4268, 4531, 796, 1758, 1832, 1077, 3488, 1827, 4810, 4136, 737, 3281, 1737, 3382, 2434, 1251, 1796, 3415, 1652, 1380, 3579, 2626, 1037, 403, 1072, 4409, 1442, 911, 4688, 2183, 1231, 3354, 4066, 2243, 4438, 3431, 1619, 2565, 1417, 2930, 1503, 1708, 1176, 3587, 2500, 1503, 4275, 766, 1187, 4975, 2330, 4315, 2233, 2532, 1364, 4189, 1245, 4213, 1981, 2552, 2361, 1176, 2646, 2413, 957, 1866, 2693, 3464, 4938, 893, 4750, 2889, 2365, 908, 876, 4292, 240, 1607, 2329, 1268, 3736, 1810, 3411, 4738, 4122, 1802, 1126, 1054, 4477, 4036, 903, 4113, 618, 4724, 448, 2157, 149, 1171, 4347, 4124, 2920, 2224, 1652, 979, 2223, 3617, 3662, 1310, 4037, 835, 1555, 347, 4409, 4196, 2725, 4247, 1678, 1114, 4461, 3483, 3759, 3271, 1958, 982, 1061, 3136, 3052, 269, 741, 2989, 1195, 384, 4755, 34, 2643, 1641, 3183, 1491, 1624, 4364, 3937, 765, 3354, 1532, 4700, 859, 325, 1798, 347, 4993, 4093, 2282, 2327, 2886, 2047, 4355, 953, 4209, 663, 1824, 1651, 4146, 288, 3166, 3547, 1010, 1821, 2184, 440, 1350, 1830, 4740, 3016, 872, 1572, 4002, 1087, 2243, 332, 952, 943, 1030, 2066, 3690, 2995, 3096, 2752, 608, 2250, 466, 2085, 2415, 7, 4529, 3776, 3550, 1266, 3814, 2075, 505, 808, 4861, 1228, 4985, 721, 1721, 3019, 514, 948, 1628, 510, 4266, 2513, 4993, 4298, 167, 2433, 3825, 3826, 615, 4197, 2748, 4810, 1216, 657, 473, 4172, 1607, 2032, 4137, 4403, 4753, 2858, 2911, 4994, 4887, 3870, 1989, 2400, 4849, 1786, 3335, 3263, 1302, 4817, 3117, 3787, 1232, 4765, 2304, 3934, 2891, 3951, 4318, 382, 4350, 1888, 2765, 27, 1989, 1228, 1391, 2597, 263, 1786, 4551, 1940, 3330, 2870, 1220, 1948, 663, 4134, 3003, 904, 1087, 4112, 1318, 4160, 4808, 3284, 1027, 2967, 3998, 1239, 2069, 3823, 1223, 2234, 910, 2318, 3203, 482, 4447, 128, 4927, 2754, 4895, 2114, 2448, 1085, 2858, 4428, 4205, 1785, 1991, 827, 3086, 3842, 4192, 4416, 2154, 1057, 3223, 682, 1750, 4575, 5, 2071, 1151, 4445, 3337, 2503, 656, 3488, 2547, 646, 1965, 2146, 4145, 3488, 1621, 1735, 3350, 4224, 1914, 4886, 78, 4953, 3906, 4982, 2197, 1152, 4519, 2452, 2401, 4573, 760, 3376, 1406, 1652, 3248, 3690, 4509, 990, 2695, 4757, 3461, 773, 4108, 3420, 2360, 2809, 1160, 1888, 850, 488, 3613, 1687, 1190, 449, 2368, 1992, 1968, 2800, 2508, 2062, 2140, 2140, 212, 2221, 2583, 3716, 243, 4263, 2961, 4647, 3031, 310, 1385, 2916, 1934, 1790, 4927, 3107, 198, 3970, 767, 3392, 3805, 4062, 4680, 1996, 661, 2607, 2426, 2626, 4177, 2972, 4580, 1733, 3955, 4992, 4404, 2906, 2694, 3080, 2207, 1478, 3515, 3575, 3901, 2137, 3859, 3293, 3417, 3596, 3566];

 console.log(mergesort(array));