목록merge-sort (1)

Computing

Algorithm) Parallel Merge sort

Merge sort 개념 다음 그림과 같이 Two pass (그림 상의 빨간색 과정과 초록색 과정)로 진행됩니다. 빨간색 과정을 Divide path, 초록색 과정을 combine path라고 하겠습니다. [Divide path] Divide path의 경우 Recursively 현재 array를 두개의 연속된 half-arrays로 분할합니다. half-array의 크기가 1이 될때까지 분할합니다. [Combine paht] Combine path의 경우 Recursively 두개의 half-arrays를 합쳐서 하나의 arrays로 정렬합니다. 이때 두 개의 half-arrays는 항상 정렬되어 있기에 두개의 half-arrays를 쉽게 정렬할 수 있습니다. (항상 정렬되어있는 이유는 귀납적으로, h..
Parallel | Distributed Computing/알고리즘 2022. 3. 10. 01:19
이전 Prev 1 Next 다음