マージソートの処理を理解する。流れを追って細かく分解。

#最少単位に分解後にmergeを行う。この処理を繰り返す
def merge_sort(arr):
  #要素が1つか０のときはその配列をそのまま返す。（比較対象がなくソートの必要性がないため）
  if len(arr) <= 1:
    return arr

  #２分割する。スライスで切り分けるため、整数部のみ抽出する
  mid = len(arr)//2

  #元の配列を２分割
  arr1 = arr[:mid]
  arr2 = arr[mid:]

  #最少単位になるまで２分割を続ける
  #returnになった時点で再帰が終了する
  arr1 = merge_sort(arr1)
  arr2 = merge_sort(arr2)

  return merge1(arr1, arr2)


#２つの要素を比較して、小さい方を先頭に並べる
def merge1(arr1,arr2):
  #マージ結果を入れる配列
  merged = []
  l_i, r_i =0,0

  while l_i < len(arr1) and r_i < len(arr2):

        if arr1[l_i] <= arr2[r_i]:
            merged.append(arr1[l_i])
            l_i += 1
        else:
            merged.append(arr2[r_i])
            r_i += 1

  if l_i < len(arr1):
      merged.extend(arr1[l_i:])
  if r_i < len(arr2):
      merged.extend(arr2[r_i:])
  return merged

list=[7,4,3,5,6,1,2]
merge_sort(list)

#[1, 2, 3, 4, 5, 6, 7]

def div_arr(arr):
  #要素が1つか０のときはその配列をそのまま返す。（比較対象がなくソートの必要性がないため）
  if len(arr) <= 1:
    return print(arr)

  #２分割する。スライスで切り分けるため、整数部のみ抽出する
  mid = len(arr)//2

  #元の配列を２分割
  arr1 = arr[:mid]
  arr2 = arr[mid:]

  #最少単位になるまで２分割を続ける
  #returnになった時点で再帰が終了する
  arr1 = div_arr(arr1)
  arr2 = div_arr(arr2)

list=[7,4,3,5,6,1,2]
div_arr(list)

[7]
[4]
[3]
[5]
[6]
[1]
[2]

def div_arr(arr):
  if len(arr) <= 1:
    return print(arr)

  mid = len(arr)//2

  arr1 = arr[:mid]

  arr1 = div_arr(arr1)

list=[7,4,3,5,6,1,2]
div_arr(list)

[7]

#２つの要素を比較して、小さい方を先頭に並べる
def merge1(arr1,arr2):
  #マージ結果を入れる配列
  #初期値0だが、mergeを繰り返す度に中身が増えていく
  merged = []

  #対比する要素の配列番号初期値
  l_i, r_i =0,0

  #ループ終了条件。どちらかの配列を全て比較仕切ったら終了
  while l_i < len(arr1) and r_i < len(arr2):

    #前方の要素の方が小さい場合
    #同じ場合は先方を優先するためイコールをつける
        if arr1[l_i] <= arr2[r_i]:
            merged.append(arr1[l_i])
            #同じ要素を再度検証しないよう配列番号に１をたす。
            l_i += 1
        else:
            merged.append(arr2[r_i])
            r_i += 1

  # while文が終了したら、追加されていない方を丸ごと答えに追加する。
  # 各配列は既に昇順にソート済みであるため、そのまま追加している。
  if l_i < len(arr1):
      merged.extend(arr1[l_i:])
  if r_i < len(arr2):
      merged.extend(arr2[r_i:])
  return merged

a=[2,3]
b=[1,8,9]

merge1(a,b)

#[1, 2, 3, 8, 9]

#ソートする配列
arr=[7,4,3,5,6]

#1回目の処理
arr1=[7,4]
arr2=[3,5,6]

#arr1を再帰
arr1`=[7]
arr2`=[4]

##arr1の解##
merge`=[4,7]


#arr2を再帰
arr1``=[3]
arr2``=[5,6]

#arr2``を再帰
arr1```=[5]
arr2```=[6]

##arr2``の解##
merge``=[5,6]

##arr2の解##
merge```=[3,5,6]


##いよいよarrの解##
merge=[3,4,5,6,7]

##arrの解はarr1とarr2をmergeしたもの
#arr1の解 merge`=[4,7]
#arr2の解 merge```=[3,5,6]

  arr1 = merge_sort(arr1)
  arr2 = merge_sort(arr2)

  return merge1(arr1, arr2)