버스타고 가다가 머릿속으로만 생각해본건데 틀린거 있으면 지적좀


일단 아이디어의 가장 기본은 


사이즈가 n인 배열을 정리하는 시간 복잡도 (대충 여기선 O(n^2)를 씀, 뭘 써도 결과는 같을듯?)를 계산할때


n을 통째로 정렬하는 것 보다 반으로 나눠서 하는게 더 빠르다. 임


n이 충분히 크고 n을 반으로 나눠서 정렬하면


[  n^2  > n^2/4 + n^2/4 + n (이건 이미 정렬된 2/n 사이즈의 배열 두개를 합치는데 필요한 시간복잡도== 2/n + 2/n)]


이런 방법으로 생각해보면 사이즈를 반씩 쪼갠 놈들도 위에랑 똑같이 반으로 쪼개서 계산할 수 있음


이런식으로 계속 반으로 나누다 보면 결국 원소가 하나만 남게 되고 정렬을 위해 하나씩 분리된 원소들을 다시 합쳐나가는


정렬을 진행하게 됨 이때 트리를 그려보면 리프노드 쪽에선 하나씩 합쳐지고 바로 위는 2개씩 그 위는 4개씩 .. 으로 원래 사이즈 n까지 올라가게 되는데

(물론 사이즈가 2^n 으로 표시되지 않을때는 꼭 2개 4개 가 딱 맞게 올라가는건 아님ㅁ)


매 스테이지마다 총 사이즈가 n인 이미 정렬된 배열들을 합치는 계산이 진행되고 트리의 사이즈는 log_2(n) 이므로


비교정렬의 하한은 O(n*log_2(n))


혹시 어디 잘못생각한 부분 있나요??