[Algorithm] 병합 정렬(merge sort)

병합 정렬(merge sort) ?

• 재귀 용법을 활용한 정렬 알고리즘
  1. 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눔
  2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬
  3. 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병

 

def merge(left, right):
  merged = list()
  left_point, right_point = 0,0
  
  #case1: left/right 둘다 데이터 있을 때
  while len(left) > left_point and len(right) > right_point:
    it left[left_point] > right[right_point]:
      merged.append(right[right_point])
      right_point += 1
    else:
      merged.append(left[left_point])
      left_point += 1
  
  #case2: left 데이터 없을 때
  while len(left) > left_point:
    merged.append(left[left_point])
    left_point += 1
  
  #case3: right 데이터 없을 때
  while len(right) > right_point:
    merged.append(right[right_point])
    right_point += 1
    
  return merged
  
def mergesplit(data):
  if len(data) <= 1:
    return data
    
  medium = int(len(data) / 2)
  left = mergesplit(data[:medium])
  right = mergesplit(data[medium:])
  
  return merge(left,right)
  
  
#------------------------------------
import random

data_list = random.sample(range(100), 10)
mergesplit(data_list)