Mergesort

According to my colleague,

MERGE SORT IS THE BEST SORT.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def mergesort(arr):
if len(arr) == 1:
return arr

mid = len(arr) // 2
left = mergesort(arr[:mid])
right = mergesort(arr[mid:])

i = j = 0

sortedArray = []
while i < len(left) and j < len(right):
if left[i] < right[j]:
sortedArray.append(left[i])
i += 1
else:
sortedArray.append(right[j])
j += 1

if i < len(left):
while i < len(left):
sortedArray.append(left[i])
i += 1

if j < len(right):
while j < len(right):
sortedArray.append(right[j])
j += 1

return sortedArray


arr = [5, 1, 3, 4]
arr2 = mergesort(arr)
print(arr2) #[1,3,4,5]