합병정렬의 시간복잡도는 O(NlogN)(또는 세타(NlogN)) 이 사실은 다들 알고 있을 겁니다.그리고 이 O(NlogN)이라는 복잡도를 어떻게 따지느냐? 다들 한번쯤 해봤을 것입니다.혹시 깔끔한 이해 없이 지나갔다면 다시 한번 천천히 해봅시다그 전에! 분할정렬 자체에 대한 개념이 모호하신 분은 이 포스팅을 읽고 다시 돌아오는 것을 추천합니다.시작!! 아래 그림 많이 보셨을 겁니다. 합병정렬!!이 합병정렬의 복잡도가 왜 NlogN인지 차근차근 설명할텐데요,순서대로 사고하면서 천천히 해봅시다먼저, 절반으로 분할해가는 과정을 봅시다.- 초기 배열의 요소수는 N개입니다.- 분할정렬 함수의 인자로는 "배열", "p", "r"이 들어옵니다. p는 분할대상인 요소가 시작하는 인덱스였죠. 초기 함수의 인자로 0이 ..

합병 정렬 (Merge sort)이란? 분할정복알고리즘 중 하나입니다. 일단 분할정복법이 뭔지 먼저 설명하는 게 좋을 듯합니다. 분할정복 (Divide and Conquer) 분할정복은 다음의 3단계로 이루어집니다. 1. Divide --- 문제를 subproblem으로 나눕니다. 2. Conquer --- 그 subproblem을 재귀적으로 주루룩 정복합니다. 이때 Base case까지 다다르게 됩니다. Base case란, subproblem이 충분히 작으면 그냥 아주 쉽게, 거의 그 자체 풀리는 수준의 케이스입니다. 3. Combine --- 2단계에서 subproblem들을 정복해 해답을 얻었습니다. 이 답들을 Combine해서 맨 처음의 original problem의 해답으로 얻어냅니다. 이것..