アルゴリズム勉強 #3 マージソートをpythonで実装する
2021.10.25
今回はマージソートです！
- 配列を2分割を繰り返す
- left, rightで1こずつになったら、小さい順からマージ
- 計算量はO(nlogn)
試したコード
## merge sort
import random
def merge_sort(array):
if len(array) == 1:
return array
mid = len(array) // 2
left = array[0:mid]
right = array[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
merged = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
if i < len(left):
merged.extend(left[i:])
else:
merged.extend(right[j:])
return merged
array = [i+1 for i in range(10)]
random.shuffle(array)
merge_sort(array)
