merge sort 합병 정렬이란?
merge sort합병 정렬을 잘 이해하기 위해서는 divide and conquer분할 정복(큰 문제가 작은 문제들의 합)에 대해 알아야한다;
split first and merge after 먼저 쪼개고 나중에 합치는 방식이다.

그림으로 이해하기

1. 카드가 한장만 남을때까지 분해하기 split first
   
2. 정렬하면서 합치기 merge after
   

코드로 작성하기

let array = [7, 2, 6, 3, 9]

func mergeSort<T: Comparable>(_ array: [T]) -> [T] {
    //split
    guard array.count>1 else { return array }   //recursion, 원소가 1개 남으면 종료한다
    let middleIndex = array.count/2
    let leftArray = mergeSort(Array(array[0..<middleIndex]))
    let rightArray = mergeSort(Array(array[middleIndex..<array.count]))
    
    return merge(leftArray, rightArray)
}

// 이렇게 구현하게 되면 left와 right가 sorted한 상태로 들어와야 한다
//func merge(_ left: [Int], _ right: [Int]) -> [Int] {
//  let combinedArray = left + right
//  return combinedArray.sorted(<)
//}

//merge
func merge<T: Comparable>(_ left: [T], _ right: [T]) -> [T] {
    var leftIndex = 0
    var rightIndex = 0
    
    var orderedArray: [T] = []
    
    //미리 비교해서 정렬하기
    while leftIndex < left.count && rightIndex < right.count {
      let leftElement = left[leftIndex]
      let rightElement = right[rightIndex]

      if leftElement < rightElement { // 2
        orderedArray.append(leftElement)
        leftIndex += 1
      } else if leftElement > rightElement { // 3
        orderedArray.append(rightElement)
        rightIndex += 1
      } else { // 4
        orderedArray.append(leftElement)
        leftIndex += 1
        orderedArray.append(rightElement)
        rightIndex += 1
      }
    }

    while leftIndex < left.count {
        orderedArray.append(left[leftIndex])
        leftIndex += 1
    }

    while rightIndex < right.count {
        orderedArray.append(right[rightIndex])
        rightIndex += 1
    }
    
    return orderedArray
}
mergeSort(array)

이해가 잘 안돼서 손으로 돌려봄

https://www.raywenderlich.com/741-swift-algorithm-club-swift-merge-sort