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 [ ]:
Content source: joaoandre/algorithms
Similar notebooks: