[알고리즘] 정렬 - 병합 정렬, O(NlogN)
병합 정렬은 문제를 더 작은 문제로 쪼개서 재귀적으로 풀이한다. 대표적인 O(NlogN) 정렬 알고리즘이다. 병합 정렬 (Merge Sort) 소개 기본적인 아이디어는 데이터를 절반으로 나눠서 전반부와 후반부를 각각 정렬해서 합치는 방식을 재귀적으로 반복하는 방식이다. 그래서 재귀호출하는 MergeSort 부분과 정렬된 두 데이터를 합치는 Merge 부분으로 나뉜다. 최종적으로 원소가 1개 남게 될 때 까지 계속 문제를 쪼갠 뒤, Merge(병합) 과정에서 순서에 맞게 데이터를 정렬하면서 두 데이터 그룹을 합치는 과정이 반복된다. 예를 들어 위 그림에서 1과 3으로 나뉘어졌다면 [1,3]으로 합쳐지고, 5와 2로 나뉘어졌다면 [2,5]로 합쳐진다. [1,3]과 [2,5]를 또 합치게 된다면 각각의 데이터..
알고리즘
2024. 3. 17. 06:29
