[알고리즘] 병합 정렬 (merge sort)

병합 정렬이란?

• 재귀용법을 활용한 정렬 알고리즘
  1. 리스트를 절반으로 자르고 비슷한 두개의 리스트로 나눈다 (나누고나누고..)
  2. 각 부분 리스트를 재귀적으로 합병정렬을 이용해 정렬한다
  3. 두 개 리스트를 다시 하나의 정렬된 리스트로 합병한다

• ex) data_list = [1, 9, 3, 2]
  • 먼저 [1,9]와 [3,2]로 나눈다
  • 앞부분은 [1]과 [9]로 나눈다
  • 정렬해서 합친다 [1,9]
  • 뒷부분은 [3]과 [2]로 나눈다
  • 정렬해서 합친다 [2,3]
  • 비교하면서 [1,9]와 [2,3]을 합친다
    • 1 < 2 : [1]
    • 9 > 2 : [1,2]
    • 9 > 3 : [1,2,3]
    • 9 : [1,2,3,9]

 

코드 구현

def merge(left, right):
	merged = list()
    left_point, right_point = 0, 0
    
    #left, right 둘 다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
        	merged.append(right[right_point])
      		right_point += 1
    	else:
        	merged.append(left[left_point])
            left_point += 1
        
    #right에 데이터가 없을때
    while len(left) > left_point:
    	merged.append(left[left_point])
        left_point += 1
    
    #left에 데이터가 없을때
    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)