병합정렬

정의

• 정렬할 배열을 절반으로 잘라 비슷한 크기의 두 부분의 배열로 나눈다. (split)
• 각 부분 배열을 재귀적으로 합병 정렬을 이용해 정렬한다. 
• 두 부분 배열을 다시 하나의 정렬된 배열로 합병한다.

// 병합정렬
func merge(left: [Int], right: [Int]) -> [Int]{
    var merged = [Int]()
    var leftPoint = 0
    var rightPoint = 0
    
    // case1 - left/right 둘다 있을때
    while left.count > leftPoint && right.count > rightPoint {
        if left[leftPoint] > right[rightPoint] {
            merged.append(right[rightPoint])
            rightPoint = rightPoint + 1
        } else {
            merged.append(left[leftPoint])
            leftPoint = leftPoint + 1
        }
    }
    
    // case2 - left 데이터가 없을 때
    while left.count > leftPoint {
        merged.append(left[leftPoint])
        leftPoint = leftPoint + 1
    }
    
    // case3 - right 데이터가 없을 때
    while right.count > rightPoint {
        merged.append(right[rightPoint])
        rightPoint = rightPoint + 1
    }
    
    return merged
}

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

print(mergeSplit(dataArray: [2,4,6,1,7,4,5,6,442,11]))

1. 배열을 mergeSplit함수에서 재귀를 통해나눌 수 있을때까지 나눈다.
2. 다 나눠지면 재귀 리턴으로 merge함수를 통해 합병정렬하면서 최종으로 정렬된 배열을 얻는다