병합 정렬

https://unsplash.com/photos/AuztPcaE6CY

병합 정렬에 대해 알아보자

 

 

 

 

 

---

얻어갈 지식

• 병합 정렬

 

 

 

 

 

병합 정렬

 

퀵 정렬과 마찬가지로 분할-정복 알고리즘이다.

어레이 크기가 1이 될 때까지 반복적으로 분할하고 크기가 1이 되면 전체 어레이가 병합될 때 까지 병합한다.

스테이블한 정렬 알고리즘이며 버블 정렬, 선택 정렬, 삽입 정렬보다 빠르지만, O(N) 만큼의 추가 메모리 공간이 필요하다.

 

아래 사진과 영상을 보고 이해해보자.

 

 

병합 정렬 사진

 

병합 정렬 동영상

 

 

코드로 작성

def mergeSort(arr):
	if len(arr) > 1:
		mid =  len(arr) // 2

		L = arr[:mid]
		R = arr[mid:]

		mergeSort(L)
		mergeSort(R)

		i = j = k = 0

		while i < len(L) and j < len(R):
			if L[i] < R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1

 

 

시간 복잡도와 보조 공간

• 분할 할 때 logN 만큼 필요하고 병합할 때 O(N)의 시간이 소요된다. 최악의 경우 O(N logN)이다.
• 보조 공간은 O(N) 만큼 필요하다.

 

 

 

 

 

---

https://www.geeksforgeeks.org/merge-sort/

Merge Sort - GeeksforGeeks