[Algorithm] 병합/합병 정렬 (Merge Sort)

🧐 병합 정렬(Merge Sort)이란?

[출처] 위키피디아

병합 정렬(Merge Sort)는 비교 기반의 정렬 알고리즘으로, 안정 정렬에 속하는 분할 정복 알고리즘이다.

 

병합 정렬의 알고리즘은 크게 분할(Divide)-정복(Conquer)-결합(Combine), 3단계로 나눌 수 있다.

대략적으로 그 과정을 설명하자면,

1. 정렬되지 않은 배열을 N개의 배열로 분할한다.
2. 배열(리스트)의 길이가 0또는 1인 경우 정렬된 것으로 여긴다. 반면, 그렇지 않은 경우 정렬되지 않은 배열을 절반으로 다시 분할 한 후, 값을 비교한다.
3. 각 부분 배열을 재귀적으로 병합 정렬하며 정렬한다.
4. 두 개의 부분 배열을 다시 하나의 정렬된 리스트로 결합한다.

병합 정렬은 알고리즘이 복잡하지만, 시간복잡도의 측면에서 좋은 효과(O(NlogN))를 보인다.

---

👩‍💻 병합 정렬 - Python 코드

def merge_sort(arr):
	if len(arr) < 2:
    	return arr

	mid = len(arr) // 2
    l_arr = merge_sort(arr[:mid]) # python의 리스트 슬라이스 기능을 이용
    h_arr = merge_sort(arr[mid:])
    
    c_arr = [] # 결합(병합) 리스트
    
    l = h = 0
    while l < len(l_arr) and h < len(h_arr):
    	if l_arr[l] < h_arr[h]:
        	c_arr.append(l_arr[l])
            l += 1
        else:
        	c_arr.append(h_arr[h])
            h += 1
    c_arr += l_arr[l:]
    c_arr += h_arr[h:] # 남는 부분을 덧붙임
    return c_arr

파이썬의 slice기능을 이용해 위와 같이 병합 정렬 알고리즘을 표현할 수 있다. 하지만, slice를 사용할 때는 배열의 복제가 일어나 메모리 사용 효율이 떨어지게 된다.

 

아래의 코드는 다른 분이 올려주신 최적화된 코드다.

def merge_sort(arr):
    def sort(low, high):
        if high - low < 2:
            return
        mid = (low + high) // 2
        sort(low, mid)
        sort(mid, high)
        merge(low, mid, high)

    def merge(low, mid, high):
        temp = []
        l, h = low, mid

        while l < mid and h < high:
            if arr[l] < arr[h]:
                temp.append(arr[l])
                l += 1
            else:
                temp.append(arr[h])
                h += 1

        while l < mid:
            temp.append(arr[l])
            l += 1
        while h < high:
            temp.append(arr[h])
            h += 1

        for i in range(low, high):
            arr[i] = temp[i - low]

    return sort(0, len(arr))

병합 정렬을 sort()와 merge()로 나눠 작성된 코드로, sort() 함수를 통해 리스트의 슬라이스를 쓰지 않고 병합정렬을 할 수 있도록 한다.

---

📜 참고

https://www.daleseo.com/sort-merge/

[알고리즘] 병합 정렬 - Merge Sort (Python, Java)