[알고리즘] 병합정렬(merge-sort) 파이썬

# 정리

merge(left,right)함수를 만들어 두 리스트를 순차적으로 비교하면서 정렬하는 것 까지는 쉽게 했는데, 이 함수들을 재귀적으로 계속 호출해서 정렬시키는 방법을 잘 모르겠어서 꽤 오랜 시간이 걸렸다. 

아직은 재귀가 익숙하지 않은거 같다.

 

# 코드

import random


def merge(left, right):
  sorted = []
  lptr, rptr = 0, 0
  while lptr < len(left) and rptr < len(right):
    if left[lptr] < right[rptr]:
      sorted.append(left[lptr])
      lptr += 1
    else:
      sorted.append(right[rptr])
      rptr += 1

  if( lptr < len(left)) :
    for i in range(lptr,len(left)) :
      sorted.append(left[i])
  elif ( rptr < len(right)) :
    for i in range(rptr, len(right)):
      sorted.append(right[i])
  print(f"merge {sorted}")
  return sorted

def merge_sort(data) :
  print("merge_sort called")
  if len(data) <= 1:
    return data
  pivot = len(data) // 2
  left = merge_sort(data[:pivot])
  right = merge_sort(data[pivot:])
  print(left,right)
  return merge(left,right)

if __name__ == '__main__':
  sample = [4, 3, 7, 2, 6, 8, 9, 0, 1, 5]
  answer = merge_sort(sample)
  print(f"sorted : {answer}")

 

#참고

코드 실행 순서 시각화 해주는 사이트

Python Tutor: Learn Python, JavaScript, C, C++, and Java by visualizing code