merge sort
-
[알고리즘] 병합 정렬 (Merge Sort)Study/자료구조,알고리즘 2022. 11. 4. 18:21
01. 병합 정렬의 개념 안정 정렬이다. 정렬을 위한 별도의 공간이 필요하다. 분할 정복 알고리즘이다. 주로 순환 호출로 구현 매우 빠른 속도를 보장 ( O(NlogN) ) 02. 과정 설명 배열을 반으로 나누는 것을 반복한다. 사이즈 1짜리 배열까지 나누고 나면, 나눈 순서의 역순으로 정렬해가며 부분 배열을 합친다. 말로는 사실 설명할 게 별로 없다... 그림으로 보는 게 더 설명이 쉬울 듯 하여 첨부 03. C++ 코드 void Merge(int*& arr, int*& tmp, int left, int right) { if (left == right) return; int l = left; int mid = (l + right) / 2; int midIdx = mid + 1; int idx = l; ..