병합정렬
-
[알고리즘] 병합 정렬알고리즘 & 자료구조 2021. 1. 21. 16:31
병합 정렬 병합 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식이다. 그리고 이 과정은 재귀적으로 구현된다. 아래의 숫자들을 오름차순으로 정렬해 보자 7 4 5 2 6 3 8 1 먼저 숫자들을 반으로 나눈다. 7 4 5 2 | 6 3 8 1 그리고 나눠진 부분 중 첫번째를 한번 더 반으로 나눈다. 7 4 | 5 2 | 6 3 8 1 마지막으로 한 번 더 나눠준다 7 | 4 | 5 2 | 6 3 8 1 이제 숫자가 7 과 4로 나뉘어져있다. 두 숫자를 병합 해보자. 단, 작은 숫자가 먼저 오도록한다 4 7 | 5 2 | 6 3 8 1 마찬가지로 5 ,2 역시 나눈 후 병합해보면 4 7 | 2 5 | 6 3 8 1 이제 4 7 | 2 5 부분을 병합 2 4 5 7..