병합 정렬은 분할 정복 기법과 재귀 알고리즘을 활용한 정렬 알고리즘이다
주어진 배열의 원소가 하나 밖에 남지 않을 때까지 분할하고, 이를 재배열하면서 원래 크기의 배열로 합병한다.
Stable 정렬이지만, 작은 단위로 쪼갠 배열을 저장할 추가 공간을 사용하기 때문에 Not-in-place 정렬이다. 하지만 인덱스 접근을 통해서 입력 배열을 업데이트하면 메모리 사용을 대폭 줄일 수 있다.(In-place Sort)
--
분할 정복
주어진 문제를 나눌 수 없을 때까지 나누고(Divide) 각각을 풀면서(Conquer) 다시 합병하여(Combine) 원래 문제의 해답을 얻는 알고리즘이다. 일반적으로 Devide를 잘 할수록 Conquer 과정이 쉬워지기 때문에 분할 과정이 중요하다.
1. 주어진 배열을 더 이상 쪼갤 수 없을 때까지 둘로 분할한다.
2. 나뉜 두 개의 배열을 하나로 합치는데, 이 때, 크기가 작은 값이 앞에 오도록 한다.
3. 배열의 크기가 기존과 같아질 때까지 병합 과정을 반복한다.
O(N)
이다.O(logN)
의 시간이 소모된다. 또한, 배열을 병합하는 과정에서 배열의 모든 원소를 비교해야 하므로 O(N)
만큼의 시간이 필요하다. 따라서 병합 정렬의 시간 복잡도는 O(NlogN)
이다.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
--