マージソート
Contents
呼称
- マージソート (merge sort)
概要
マージソートは安定ソートであり、配列を分割統治法により並べ替えるアルゴリズムである。
アルゴリズム
- 配列を分割する (通常二等分する)
- 分割された各配列で、配列長が1個ならそのまま返し、配列長が2個以上なら再帰的に分割する。
- 分割された配列は、統合時に並び替えられる。
実装例
Python 3
def merge_sort(arr):
arr = arr.copy()
_merge_sort(arr, 0, len(arr))
return arr
def _merge_sort(arr, l, r):
if r - l == 1:
return
m = (l + r) // 2
_merge_sort(arr, l, m)
_merge_sort(arr, m, r)
_merge(arr, l, m, r)
def _merge(arr, l, m, r):
l_arr = arr[l:m]
r_arr = arr[m:r]
i = 0
j = 0
while i < len(l_arr) and j < len(r_arr):
if l_arr[i] < r_arr[j]:
arr[l+i+j] = l_arr[i]
i += 1
else:
arr[l+i+j] = r_arr[j]
j += 1
while i < len(l_arr):
arr[l+i+j] = l_arr[i]
i += 1
while j < len(r_arr):
arr[l+i+j] = r_arr[j]
j += 1