[공유] 합병정렬

출처 오분쯤 느린 시계|영양 데이터의 정렬 방법 중 항상 n log n 의 수행시간을 가지는 알고리즘이 있다. 그것이 바로 이번에 설명할 합병 정렬(Merge Sort)이다. 합병 정렬의 기본 알고리즘은 두 개의 정렬된 리스트를 가지고 하나의 정렬 리스트로 합병한다. 예를들면 1,2,3,7,8 과 4,5,6 이라는 두개의 정렬된 리스트가 있다고 할 경우 이 두개의 리스트는 이미 정렬되어 있는 상태이기 때문에 각각의 키의 크기를 비교하면서 1,2,3,4,5,6,7,8 이라는 하나의 리스트로 합병하는 것은 간단하게 만들 수 있을 것이다. 두 개의 정렬된 리스트를 하나의 정렬 리스트로 합병 합병 정렬에서는 입력으로 들어가는 리스트를 나누는 방식에 따라 몇가지의 다른 방법이 있다. 여기서 다룰 방법은 반복 합병 정렬이다. 반복 합병 정렬은 입력 리스트를 길이가 1인 n개의 정렬 리스트로 간주한다. 이 리스트들을 크기가 2인 n/2 개의 리스트를 얻기 위해 쌍쌍으로 합병하고, 같은 방식으로 ...

원문링크 : [공유] 합병정렬