컴공생의 다이어리

병합 정렬(Merge Sort) 병합 정렬은 분할 정복 알고리즘의 하나로 합병 정렬이라고도 한다. 불안정 정렬인 퀵 정렬과 달리, 병합 정렬은 안정 정렬에 속한다. 전체 데이터를 가장 작은 단위로 분할한 후 분할한 데이터를 다시 병합하면서 정렬하는 재귀용법을 활용한 정렬 알고리즘이다. 퀵 정렬과 비교했을 때, 차이점은 아래와 같다. 퀵 정렬 - 각 요소를 피벗과 비교하여 요소를 정렬 - 피벗을 통해 정렬(partition) → 영역을 쪼갬(quick sort) 병합 정렬 - 배열을 하나의 요소가 남을 때까지 두 개의 하위 배열 (n / 2)로 반복하여 나눔 - 영역을 쪼갤 수 있을 만큼 쪼갬(merge sort) → 정렬(merge) 정렬 과정 분할(Divide) 단계 리스트를 절반으로 나누어 비슷한 크..