Merge Sort : Alalysis

Divide and Conquer, Sorting and Searching, and Randomized Algorithms

by Stanford University

의 Merge Sort : Analysis

정의 Merge sort는 6nlogn+6n의 operation을 갖는다. (n은 array의 수의 갯수)

먼저 한 번의 리컬시브에서 계산량을 구한다.

• operation의 수는 4m + 2

• i, j assign

• m번 루프

• k assign

• 배열 카피
  

• i 또는 j의 증가

• m이 1보다 크거나 같다고 가정했을떄 6m 보다 작거나 같다

• 계산의 편의를 위해 6m으로 사용
  

다음은 총 리컬시브의 양을 구한다.

• subproblem의 수는 2^n (맨 마지막 level의 노드 수)

• 각 node의 사이즈는 n/2^n

• 한 리컬시브 계산량이 6m이므로
  
• 총 subproblems * 한 리컬시브 계산량 * array 사이즈 = 6n

6n * 총 level의 수 = 6n(logn +1), 가정이 맞다!!