• Merge Sort (합병정렬) 은 정렬알고리즘 중 가장 빠른 알고리즘 중 하나이다.
  → O(n logn)
  
• 합병 정렬의 기본 아이디어는 <divide and conquer> 이다.
• 먼저 나눈 후, 이후에 병합한다.

작동방식

이렇게 정렬되지 않은 카드가 있다고 가정하자.

구현

• mergeSort

public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {
	let middle = array.count / 2
	let left = Array(array[..<middle])
	let right = Array(array[middle...])
	// ...
}

Split

public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {

	// 1. 
	guard array.count > 1 else { return array }

	let middle = array.count / 2
	
	// 2. 
	let left = mergeSort(Array(array[..<middle]))
	let right = mergeSort(Array(array[middle...]))
	// ...
}

1. 재귀의 탈출 조건

   → 배열이 오직 하나의 원소만 가질 때 재귀 탈출함

2. 쪼갠 배열을 다시 쪼개기 위해 mergeSort 자신을 반복해서 호출함. 이건 언제 멈춘다? → 요소가 하나만 남았을때!!

Merge

• left, right 배열을 병합하는게 마지막 단계이다.
• merge 메서드에서는 두 개의 정렬된 배열을 취해서, 정렬 순서를 유지하며 병합한다.

private func merge<Element>(_ left: [Element], _ right: [Element]) -> [Element] where Element: Comparable {

	// 1. 진행사항을 따라가기 위한 인덱스 변수 선언 및 초기화 
	// 처음부터 비교를 시작한다. 
	var leftIndex = 0
	var rightIndex = 0
	
	// 2. 병합된 배열
	var result: [Element] = []
	
	// 3. leftIndex가 left배열의 끝에 도달하지 않았고, 
	// rightIndex가 right 배열의 끝에 도달하지 않았을 때 
	**while leftIndex < left.count && rightIndex < right.count {**
	
		// 처음부터 시작해서 계속 왼, 오 요소를 비교한다
		let leftElement = left[leftIndex]
		let rightElement = right[rightIndex]
	
		// 4. 두 배열의 각 요소를 비교했을 때 더 작은게 result로 들어간다. 
		// 같으면 둘 다 들어간다. 
		if leftElement < rightElement {
			result.append(leftElement)
			leftIndex += 1
		} else if leftElement > rightElement {
			result.append(rightElement)
			rightIndex += 1
		} else { // 같으면 둘 다 추가하고 모두 index 증가한다. 
			result.append(leftElement)
			leftIndex += 1
			result.append(rightElement)
			rightIndex += 1
		}
	}
	
	// 여기서 3번 while 문이 종료되면, 어느 한 쪽 배열의 요소는 모두 처리된 상태이다 
	// -> 일단 적어도 하나는 index가 배열의 끝에 도달했기 때문에 while 문을 탈출한 것일 테니까 
	
	//5. 나머지 요소가 남아있는 배열이 있을 수 있으므로, 남은 요소들을 모두 result 에 추가하는 과정 
	// leftIdnex가 아직 left 배열의 끝에 도달하지 않았다면, 그 나머지를 result에 추가 
	if leftIndex < left.count {
		result.append(contentsOf: left[leftIndex...])
	} 
	
	// 오른쪽도 마찬가지로 끝나지 않고 남은 요소들을 result에 추가 
	if rightIndex < right.count {
		result.append(contentsOf: right[rightIndex...])
	}
	return result 
}

이제 merge() 호출

public func mergeSort<Element>(_ array: [Element]) -> [Element] where Element: Comparable {

	guard array.count > 1 else { return array }

	let middle = array.count / 2
	

	let left = mergeSort(Array(array[..<middle]))
	let right = mergeSort(Array(array[middle...]))

	return merge(left, right)
}

Summary of Merge Sort

구현

1. divide and conquer 전략으로 많은 작은 문제를 해결해볼 수 있다.
2. 두 개의 주요 책임이 있음!
   1. divide 하기 위한 메서드 (재귀적으로 초기배열을 나눔)
   2. 두 개의 정렬된 배열을 병합하고, 하나의 정렬된 배열을 생성하는 merging method

성능

• 시간복잡도

  1. 재귀적 분할 → 레벨수가 log(n) 이므로 log(n)
  2. 각 재귀 단계에서의 비용 → 모든 요소를 병합하므로 O(n) 비용 소요
  • 총 비용
    • O(logn) x O(n) = O(nlogn)

• 공간복잡도

  • 병합정렬은 다른 정렬 알고리즘과 달리 추가적인 메모리 할당해 작업을 수행함
  • 각 레벨에서 사용되는 n 개의 요소 x log(n) 레벨의 재귀 → O(nlogn) 의 공간복잡도 가짐
    
    
    ⇒ 메모리 최적화 통해 사용하지 않는 메모리 버리면 O(n) 까지 줄일 수 있음.

    (In-Place 알고리즘 > 추가적인 메모리 공간 거의 사용하지 않고 직접 수정해 문제를 해결하는 알고리즘)!