[Algorithm] 병합 정렬 - Merge Sort (Python)

📌 병합 정렬

병합 정렬은 분할 정복 기법과 재귀 알고리즘을 활용한 정렬 알고리즘이다

주어진 배열의 원소가 하나 밖에 남지 않을 때까지 분할하고, 이를 재배열하면서 원래 크기의 배열로 합병한다.

Stable 정렬이지만, 작은 단위로 쪼갠 배열을 저장할 추가 공간을 사용하기 때문에 Not-in-place 정렬이다. 하지만 인덱스 접근을 통해서 입력 배열을 업데이트하면 메모리 사용을 대폭 줄일 수 있다.(In-place Sort)

--

분할 정복

주어진 문제를 나눌 수 없을 때까지 나누고(Divide) 각각을 풀면서(Conquer) 다시 합병하여(Combine) 원래 문제의 해답을 얻는 알고리즘이다. 일반적으로 Devide를 잘 할수록 Conquer 과정이 쉬워지기 때문에 분할 과정이 중요하다.

아이디어

1. 주어진 배열을 더 이상 쪼갤 수 없을 때까지 둘로 분할한다.
2. 나뉜 두 개의 배열을 하나로 합치는데, 이 때, 크기가 작은 값이 앞에 오도록 한다.
3. 배열의 크기가 기존과 같아질 때까지 병합 과정을 반복한다.

복잡도 분석

• 분할된 배열을 병합하는 과정에서 병합 결과를 저장할 새로운 배열이 필요하다. 따라서 공간 복잡도는 O(N)이다.
  
  
• 배열을 분할하면서 반복의 횟수는 점점 절반으로 줄어들기 때문에 O(logN)의 시간이 소모된다. 또한, 배열을 병합하는 과정에서 배열의 모든 원소를 비교해야 하므로 O(N) 만큼의 시간이 필요하다. 따라서 병합 정렬의 시간 복잡도는 O(NlogN)이다.
  
  

특징

👍 장점

• 항상 일정한 시간 복잡도를 갖는다.
• 상당히 안정성을 보이기 때문에 대부분의 경우에 좋은 성능을 낸다.
• 인접한 값들 간의 자리 교환(swap)이 발생하지 않는다.

👎 단점

• 배열 자료구조를 사용할 경우 추가적인 메모리가 발생한다.

구현

def merge_sort(arr, first, last):
	if first >= last:
		return

	merge_sort(arr, first, (first+last)//2)
	merge_sort(arr, (first+last)//2+1, last)

	return sorting(arr, first, last)


def sorting(arr, first, last):
	mid = (first + last) // 2
	i, j = first, mid+1
	temp = []

	while i <= mid and j <= last:
		if arr[i] <= arr[j]:
			temp.append(arr[i])
			i += 1

		else:
			temp.append(arr[j])
			j += 1

	while i <= mid:
		temp.append(arr[i])
		i += 1

	while j <= last:
		temp.append(arr[j])
		j += 1

	for k in range(first, last+1):
		arr[k] = temp[k-first]

	return arr

--

참고 사이트

🙇🏻‍♂️ https://www.daleseo.com/sort-merge/