병합

병합 정렬(merge sort)

📔 병합 정렬(merge sort) 이란 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵정렬과 비슷 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법. 보통 재귀함수 호출을 이용하여 구한다. 퀵정렬과 다른 점이 있다면 퀵정렬의 경우 pivot값에 따라 편향되게 분할 될 수 있는 가능성이 있기 때문에 최악의 경우 O(n^2)의 시간복잡도를 가진다. 그러나 병합정렬의 경우 정확히 반씩 나눈다는 점에서 최악의 경우에도 O(nlogn)의 시간복잡도를 보장한다. 만약 8개의 숫자를 정렬한다고 하자. 8에서 4로 나누고, 4에서 2로 나누고, 2에서 1로 나눈다. 즉 3번 나눴다. 그러므로 나누는 것은 3 = log8 이므로 logn이다. 나..