[알고리즘] 병합정렬

병합정렬(Merge Sort)

• 재귀용법을 이용한 정렬 알고리즘

방법

1. 배열을 절반으로 계속 나눈다(원소가 1개가 될때까지 재귀적으로)
2. 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다

---

구현

Python

• merge_split

def merge_split(data):
    if len(data) <= 1:
        return data
    medium = int(len(data) / 2)
    left = mergesplit(data[:medium])
    right = mergesplit(data[medium:])
    return merge(left, right)

• merge

def merge(left, right):
    merged = list()
    left_point, right_point = 0, 0
    
    # case1 - left/right 둘다 있을때
    while len(left) > left_point and len(right) > right_point:
        if left[left_point] > right[right_point]:
            merged.append(right[right_point])
            right_point += 1
        else:
            merged.append(left[left_point])
            left_point += 1

    # case2 - left 데이터가 없을 때
    while len(left) > left_point:
        merged.append(left[left_point])
        left_point += 1
        
    # case3 - right 데이터가 없을 때
    while len(right) > right_point:
        merged.append(right[right_point])
        right_point += 1
    
    return merged

Swift

• mergeSplit

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

• merge

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

테스트

var data = [44, 55, 72, 83, 74, 57, 86, 71, 85, 75, 17, 67, 59, 82, 7, 88, 13, 68, 19]

print(mergeSplit(data))
// [7, 13, 17, 19, 44, 55, 57, 59, 67, 68, 71, 72, 74, 75, 82, 83, 85, 86, 88]