[Data Structure / Algorithms] Merge Sort

주제: 빠른 정렬 알고리즘 중 하나

---

Merge Sort

• Merge Sort는 O(n log n)의 시간복잡도를 나타내며 일반적인 정렬 중에서 가장 빠른 정렬 중 하나이다.
• 병합 정렬의 기본적인 방식은 divid and conquer이며, 이는 큰 문제를 작은 문제들로 쪼개서 해결하기 쉽게 만든 후 해결한 문제들을 다시 병합하는 것이다.

1. 먼저 배열을 반으로 나눈다. 그렇게 되면 두 개의 정렬되지 않은 배열이 생긴다.
2. 이제 이 배열이 더 이상 나눌 수 없을 때까지 계속해서 반으로 나눈다. 마지막에는 각 각 하나의(정렬된) 배열이 남게 된다.
3. 마지막으로, 반대로 병합한다. 병합하면서 배열의 내부 값을 정렬하면서 병합한다.

구현

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)
}

private func merge<Element>(_ let1:[Element], _ right1:[Element]) -> [Element] where Element: Comparable { 
	var leftInedx = 0 
	var rightIndex = 0
	
	var result: [Element] = [] 
	
	while leftInedx < left1.count && rightIndex < right1.count { 
		let leftElement = left1[leftIndex]
		let rightElement = right1[rightIndex]
		
		if leftElement  < rightElement { 
			result.append(leftElement)
			leftInedx += 1 
		} else if leftElement > rightElement { 
			result.append(rightElement)
			rightIndex += 1
		} else { 
			result.append(leftElement)
			result.append(rightElement)
			leftIndex += 1
			rightIndex += 1
		}
	}
	
	if leftIndex < left1.count { 
		result.append(contentsOf: left1[leftIndex...])
	}
	
	if rightIndex < right1.count { 
		result.append(contentsOf: right1[rightIndex...])
	}
	
	return result 
}

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

mergeSort(array)

left  [7]
right  [2]
result  [2, 7]
left  [3]
right  [9]
result  [3, 9]
left  [6]
right  [3, 9]
result  [3, 6, 9]
left  [2, 7]
right  [3, 6, 9]
result  [2, 3, 6, 7, 9]

출처(참고문헌)

• https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/28-merge-sort

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다.