[Algorithm][Python] 병합 정렬 (merge sort)

1. 병합 정렬 (merge sort)

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

직접 눈으로 보면 더 이해가 쉽다: https://visualgo.net/en/sorting

출처: 위키피디아

2. 알고리즘 이해

• 데이터가 4개 일때 (데이터 갯수에 따라 복잡도가 떨어지는 것은 아니므로, 네 개로 바로 로직을 이해해보자)
• 적은 개수로 이해해서 전체적으로 적용하는 방법이 뭐더라… 동적 계획법이었다!
• ex) data_list = [1, 9, 3, 2]
  • [1, 9] , [3, 2]
  • [1], [9], [3], [2]
  • [1, 9], [3], [2]
  • [1, 9], [2, 3]
  • 이제 [1,9] 와 [2,3] 을 합친다.
    • 가장 앞쪽 요소부터 비교해서 , 새로운 배열을 return 한다.
    • 나같은 경우 sorted = list()라고 선언하고 하겠다.
    • 1 < 2 이므로, sorted = [1]
    • 9 > 2 이므로, sorted = [1, 2]
    • 9 > 3 이므로 sorted = [1, 2, 3]
    • 9밖에 남지않음 (right 는 데이터가 더이상 없음) sorted = [1, 2, 3, 9]

3. 알고리즘 구현

• 함수는 두개가 있다.
  • 배열을 쪼개는 split 함수
  • 쪼개진 함수를 합치는 merge 함수
  • 수도코드로 작성해볼까? 코드단위로 작성해보자.

1. mergesplit 함수 만들기

   • 만약 리스트 갯수가 한개 이하면 해당 값 리턴
   • 그렇지 않으면 리스트를 앞뒤로 나누기
   • left = mergesplit(앞)
   • right = mergesplit(뒤)
   • return merge(left, right)

2. merge 함수 만들기

   • 리스트 변수 하나 만들기(새로 만들 list ) sorted = list()
   • left 와 right 를 순회할 변수 두개 생성 (left_index, right_index)
   • while len(left) > left_index and len(right) >right_index
   • 왼쪽이 데이터가 없을 수도, 오른쪽이 없을 경우도 고려해야한다. 즉 while 문을 탈출했지만 , 왼쪽이나 오른쪽에 데이터가 치우쳐서 남아있는경우도 처리.
   • if len(left) > left_index 인 경우와 if len(right) > right_index 인경우를 고려하자.

4. 최종코드 작성해보기

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

def merge(left, right):
	sorted = list()
	left_index, right_index = 0 ,0
	while len(left) > left_index and len(right) > right_index:
		if left[left_index] < right[right_index]:
			sorted.append(left[left_index])
			left_index += 1
		else:
			sorted.append(right[right_index])
			right_index += 1

	# 왼쪽 데이터가 없는경우
	while len(right) > right_index:
		sorted.append(right[right_index])
		right_index += 1

	# 오른쪽 데이터가 없는경우
	while len(left) > left_index:
		sorted.append(left[left_index])
		left_index += 1

	return sorted