자료구조 총괄과제

1. 합병 정렬은 무엇인가

합병 정렬은 대표적인 정렬 알고리즘 중 하나로, 분할 정복 알고리즘에 기초한 방식으로 작동한다. 이 알고리즘은 효율적인 정렬을 위해 데이터를 일정한 크기로 분할하고, 정렬된 두 개의 부분집합을 합쳐 최종적으로 정렬된 전체 집합을 생성하는 과정으로 이루어진다. 합병 정렬은 안정적 정렬로 알려져 있으며, 일반적으로 O(n log n)의 시간 복잡도를 가진다. 합병 정렬은 먼저 주어진 배열을 두 개의 부분 배열로 나누는 것으로 시작한다. 이 과정은 배열의 크기가 1이 될 때까지 재귀적으로 반복된다. 배열의 크기가 1이 되면 그 자체로 정렬된 상태가 되므로 더 이상 나눌 필요가 없다. 이렇게 쪼개진 작은 배열들을 차례로 정렬된 상태로 합쳐 나가기 위해서는 `합병` 과정이 필요하다. 두 개의 정렬된 배열을 합치는 과정에서, 두 배열의 최솟값을 비교하여 더 작은 값을 새로운 배열에 추가하는 방식으로 진행된다. 이 과정을 반복하면 두 개의 배열을 합쳐 하나의 정렬된 배열을 만들 수 있다. 합병 정렬을 사용할 때, 전체 알고리즘의 흐름은 다음과 같다. 처음에 전체 배열을 반으로 나눈다. 각부분 배열이 다시 반으로 나뉘어지고,…