MergeSort(병합정렬)-알고리즘06

MergeSort(병합정렬) 분할정복(devide and conquer)이라는 알고리즘 설계 패러다임을 이용한 대표적인 알고리즘이다. 즉, 어떤 문제(problems)를 재귀적으로 분할해 나가서 subproblems(부분문제?)들을 이용해 문제를 해결하고 다시 합치는 개념이다. 다음 사진에서 빨간부분이 분할단계, 초록부분이 합치는 단계이다. 분할을 해서 값을 비교하여 정렬하고 다시 합치는 로직이다. 알고리즘 정렬할 데이터의 크기가 0 또는 1이면 이미 정렬 된 것으로 본다. (사진에서 회색부분) 크기가 2 이상이면 반으로 쪼갠다. 1~2반복...(빨간색 부분) 원래 같은 집합에서 나온 데이터 집합 둘을 합치는데 정렬 순서를 맞춰서 합친다.(초록색 부분) 4 반복 시간복잡도 병합정렬을 재귀식으로 나타내면 ..

2023.08.13