인 이유가 여기 잘 설명이 되어 있습니다. 입력 값의 갯수가 N 개라면 log2N 번 쪼개질 수 있으므로 단계는 (log2N + 1) 만큼 일겁니다. 그런데 실제로 각 단계에서 전체 연산의 수는 6N으로 일정하므로, O(6N * (log2N + 1)) = O(logn) 이네요. 재밌는 사실은 답변에서 머지소트의 각 단계에서 몇 N 으로 연산이 일어나는가를 판단하기 위해 사용한 식이 조금 잘못된 것 같습니다. Left Subproblem 의 모든 원소들이 Right 것 보다 작으면 범위 오류가 날텐데!

하지만 N^2 은 아니고 k * N 이므로 결과적으로는 같은 값입니다.