[Algorithm] Merge Sort, 병합 정렬

What is it

병합 정렬은 재귀 용법을 활용한 정렬 알고리즘으로, 전체 원소를 가장 작은 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬 방식이다. 분할정복(Divide and Conquer) 방식을 사용한다.

아래의 애니메이션도 참고해보자!
출처 visualgo.net/sorting

How to works it

병합 정렬은 다음과 같이 작동한다.

1. 리스트의 길이가 1 이하이면 이미 정렬된 것으로 보고 그대로 데이터 리턴. 그렇지 않은 경우에는
2. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
3. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
4. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

아래 그림처럼 큰 덩어리를 쪼개는 split 부분과 쪼개진 원소를 합치는 merge 부분을 나눠서 처리한다

위 동작방식을 기반으로 각 메서드에 필요한 과정을 적어본다면

Split

• 데이터 1개일 땐 해당 데이터 리턴
• 데이터 왼쪽 부분과 오른쪽 부분을 반으로 쪼갠다(데이터가 1개가 될때까지)

Merge

• 왼쪽 데이터와 오른쪽 데이터를 비교해서
• 작은 순서로 삽입
• 더 삽입할 데이터 없으면 끝

Let's make it Code

병합 정렬은 한개의 메서드로 동작됐던 다른 정렬 알고리즘과 달리 앞에서 알아본 것 처럼 split하고 merge 하는 두개의 메서드가 필요하다!

split

func split(data: [Int]) -> [Int] {
    if data.count <= 1 { return data } 	//#1
    
    let medium = Int(data.count / 2)	//#2
    
    let left = split(data: Array(data[0..<medium])) 	//#3
    let right = split(data: Array(data[medium...]))
    
    return merge(left, right)	//#4
}

#1
데이터의 길이가 1이하일 땐 데이터 그대로 리턴

#2
데이터 길이의 중간을 구한다

#3
배열 left 에 0번 인덱스부터 medium인덱스 전까지,
배열 right에 medium인덱스 부터 배열 끝까지 분할한다

#4
쪼개진 배열이 병합되도록 merge(_:_:) 를 리턴한다

merge

func merge(_ left: [Int], _ right: [Int]) -> [Int] {
    var merged: [Int] = []	//#1
    var leftPoint = 0		//#2
    var rightPoint = 0
    
    //#3
    while left.count > leftPoint, right.count > rightPoint {
        if left[leftPoint] > right[rightPoint] {	//#4
            merged.append(right[rightPoint])
            rightPoint += 1
        }else {
            merged.append(left[leftPoint])
            leftPoint += 1
        }
    }
    
    //#5
    while left.count > leftPoint {
        merged.append(left[leftPoint])
        leftPoint += 1
    }
    
    while right.count > rightPoint {
        merged.append(right[rightPoint])
        rightPoint += 1
    }
    
    return merged
}

#1
정렬된 데이터를 담을 빈 배열 생성

#2
각 배열의 인덱스를 가리킬 변수 생성

#3
배열 left 와 right 에 둘다에 데이터가 남아 있는 경우

#4
더 작은 값을 판단해 merged에 append 하고
point 값은 1 증가시킨다

#5
배열 left 와 right 둘 중 하나에만 데이터가 남아 있는 경우

print(split(data: [4,5,1,2,3,7]))	//1,2,3,4,5,7

실행해보면 원하는대로 잘 정렬되어 나오는 것을 볼 수 있다 :)

References

• https://ko.wikipedia.org/wiki/합병_정렬