归并排序

merge_sort.py

# !/usr/bin/python3
# coding=utf-8

# Time: O(n*logn)
# Space: O(n)

# 合并
def merge(l1, l2):
  index1 = index2 = 0
  r = []
  while index1 < len(l1) and index2 < len(l2):
    if l1[index1] < l2[index2]:
      r.append(l1[index1])
      index1 += 1
    else:
      r.append(l2[index2])
      index2 += 1
  if index1 == len(l1):
    r += l2[index2:]
  if index2 == len(l2):
    r += l1[index1:]
  return r

# 分解
def merge_sort(l):
  if len(l) <= 1:
    return l
  middle = len(l) // 2
  l1 = merge_sort(l[:middle])
  l2 = merge_sort(l[middle:])
  return merge(l1, l2)

if __name__ == "__main__":
  arr = [3,5,1,6,8,4,9]
  sorted_arr = merge_sort(arr)
  print(sorted_arr)