c++알고리즘 병합정렬1 알고리즘 병합 정렬 완벽 이해하기 병합 정렬이란? 병합 정렬은 나누고 붙이는 과정을 기반으로 한 정렬 알고리즘이다. 하나의 배열을 둘로 나누고, 이를 정렬하여 다시 붙이게 된다. 병합 정렬은 재귀 함수 호출로 정렬할 수 있는 데, 배열을 1/2씩 최대한 쪼갠 후 쪼개진 배열을 정렬하고, 최대한 쪼개진 배열을 둘씩 붙이고, 다시 정렬하고, 다시 붙이고...를 반복한다. 사실 설명보다 아래 그림을 이해하는 편이 더 쉽다. 이 정렬 방식은 최악, 최선 어느 경우에도 O(Nlong(N))의 시간 복잡도를 가진다. 공간 복잡도는 O(n)이다. 코드 부분 부분 해설 코드는 아래와 같은 형식으로 풀 수 있다. 1. 반으로 최대한 쪼갤 수 있을 때까지 쪼갠다. (재귀 함수 호출, 더 쪼갤 수 없을 때는 리턴) 2. 정렬의 가장 왼쪽을 가리키는 값(p1.. 2022. 10. 29. 이전 1 다음
