알고리즘 과제 3 Sort & Stassen`s Algorithm

1) 헤더 및 소스코드

2) 실행결과
1. Merge Sort

Merge Sort는 분할 정복(divide and conquer) 기법을 기반으로 하는 정렬 알고리즘이다. 데이터 집합을 반으로 나누고, 각 부분을 재귀적으로 정렬한 후, 정렬된 두 부분을 다시 병합하여 최종적으로 정렬된 배열을 만드는 방식으로 작동한다. 이 알고리즘은 안정적(stable)이며, 최악의 경우와 평균 경우 모두 O(n log n)의 시간 복잡도를 가진다. Merge Sort의 가장 큰 장점은 큰 데이터 세트를 다룰 때도 일관된 성능을 발휘한다는 점이다. Merge Sort의 과정은 다음과 같이 설명된다. 주어진 배열의 길이가 1보다 크면 배열을 두 개의 하위 배열로 나누는데, 이때 중앙 인덱스를 기준으로 나눈다. 이런 방식으로 무한히 재귀적으로 나누어지면 결국 각 하위 배열은 하나의 원소를 갖게 되며, 이는 자동적으로 정렬된 상태로 간주된다. 그 다음에는 이러한 하위 배열들을 병합하는 과정이 진행된다. 병합 과정은 두 개의 정렬된 배열을 입력받아 하나의 정렬된 배열로 합치는 작업이며, 이때 두 배열의 원소를 비교하며 더 작은 원소를 먼저 새로운 배열에 추가한다. 이 과정을 통해 모든 요소가 병합될 때까지 반…