[알고리즘 이론] 병합 정렬 (Merge Sort)

병합 정렬(Merge Sort)

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

출처 : https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC

 

 

""" 병합 정렬 구현 코드 """

def merge(left, right):
	merged_list = list()
	l_point, r_point = 0, 0

	# Case 1. left, right 둘 다 있는 경우
	while len(left) > l_point and len(right) > r_point:
		if left[l_point] > right[r_point]:
			merged_list.append(right[r_point])
			r_point += 1
		else:
			merged_list.append(left[l_point])
			l_point += 1

	# Case 2. left 데이터가 없는 경우
	while len(left) > l_point:
			merged_list.append(left[l_point])
			l_point += 1
	
	# Case 3. right 데이터가 없는 경우
	while len(right) > r_point:
		merged_list.append(right[r_point])
		r_point += 1

	return merged_list

def merge_split(data):
	if len(data) <= 1:
		return data
	medium = int(len(data)/2)
	left = merge_split(data[:medium])
	right = merge_split(data[medium:])
	return merge(left, right)

import random

data_list = random.sample(range(100), 10) # 랜덤으로 10개 데이터 추출해서 리스트 생성
merge_split(data_list) # 병합 정렬

 

 

• 시뮬레이션 사이트

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)