defmerge_sort(arr) ->list:
iflen(arr) <=1:
return arr
pivot =int(len(arr) /2)
return merge(merge_sort(arr[:pivot]), merge_sort(arr[pivot:]))
defmerge(arr1, arr2) ->list:
ret =list()
len1 =len(arr1)
len2 =len(arr2)
i = j =0 arr1_val = arr1[i]
arr2_val = arr2[j]
whilelen(ret) < len1 + len2:
if arr1_val < arr2_val:
ret.append(arr1_val)
if i < len1 -1:
i +=1 arr1_val = arr1[i]
else:
arr1_val =float('inf')
elif arr1_val >= arr2_val:
ret.append(arr2_val)
if j < len2 -1:
j +=1 arr2_val = arr2[j]
else:
arr2_val =float('inf')
return ret
if __name__ =='__main__':
a = [1, 3, 2, 4, 7, 6, 8, 5]
print(merge_sort(a))
[1, 2, 3, 4, 5, 6, 7, 8]
基数ソート
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
defradix_sort(a):
d =len(str(max(a)))
for i inrange(0, d):
bucket = [[] for _ inrange(10)]
for e in a:
v = (int(e %10**(i +1) /10**i))
bucket[v].append(e)
j =0for lis in bucket:
for e in lis:
a[j] = e
j +=1a = [250, 900, 123, 800, 143, 700, 600, 501]
radix_sort(a)
print(a)