병합 정렬
-
Merge / Quick / Heap Sort (Medium)알고리즘/Sort 2021. 1. 5. 16:22
출처(위키피디아/GeeksforGeeks) 1. Merge Sort(병합 정렬) - 분할 정복 알고리즘. - 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (원소가 하나인 리스트는 정렬된 것과 같으므로) - 부분 리스트가 하나만 남을때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. - 마지막 남은 부분리스트가 정렬된 리스트이다. - Stable / Not in place 최악 시간복잡도 Θ( n log n ) 최선 시간복잡도 Θ( n log n ) 평균 시간복잡도 Θ( n log n ) 공간 복잡도 Θ( n ) void merge(int arr[], int l, int m, int r){ int n1 = m - l + 1; int n2 = r - m; int L[n1], R[n..