divide & conquer algorithm

1. Divide : 문제를 작은 문제로 나눈다.

2. Conquer : 작은 문제들을 재귀로 해결한다.

3. Combine : 답을 모두 합친다.

 

merge sort

1. divide : p와 r사이에서 q의 위치를 찾는다. p와 r을 더하고 2로 나누고 내려간다.

2. Conquer : 윗 단계에서 만들어진 subarrays를 재귀적으로 정렬

3. Combine : 정렬된 subarrays를 하나의 정렬된 array로 만듦

 

ex) array=[14, 7, 3, 12, 9, 11, 6, 2] (p=0 and r=7)

1. divide : q=3

2. conquer : array[0..3]=[14, 7, 3, 12] and array[4..7]=[9, 11, 6, 2]

[3, 7, 12, 14], [2, 6, 9, 11]

3. combine : [2, 3, 6, 7, 9, 11, 12, 14]