
[Algorithm/Divide&Conquer] 03. Merge Sort(병합 정렬)
·
Computer Science/Algorithm
분할 정복을 이용한 정렬 알고리즘유명한 알고리즘 문제 중의 하나인 정렬(sorting)을 분할 정복으로 구현하는 방법에 대해 알아보자 정렬 알고리즘 구현에 있어 필요한 요구사항모든 데이터 타입에 대해 동작해야 한다. 심지어 C++ 구조체, 클래스에 대해서도 서로 다른 멤버를 기준으로 정렬할 수 있어야 한다많은 양의 데이터를 처리할 수 있어야 한다.점근적 시간 복잡도 측면이나 실제 동작 시에 빠르게 동작한다현실적으로 두 번째와 세 번째 요구사항을 동시에 만족하기는 어렵다. 두 번째 요구사항은 외부 정렬(external sorting), 즉 컴퓨터의 메모리에 데이터가 상주하지 않은 상태에서 수행되는 정렬을 필요로 한다.외부 정렬 알고리즘은 실행 중 임의 시점에서 전체 데이터의 일부만을 메모리에 올려놓고 동작..