Mergesort

이번 포스팅 내용은 Merge Sort 의 정확성을 증명해보는 것이다. Divide and Conquer - 분할 정복 입력을 나누어 더 작은 문제를 물고, 작은 문제들의 답을 조합해 전체 문제의 답을 만든다. 아주 작은 문제는 어쨌거나 풀린다. mergeSort는 분할 정복 기법을 사용한다. 문제를 더 작은 문제로 나누고, 답을 합칠 때(merge) 재귀가 사용된다. 위처럼 "이미 Sorted 된 두 배열을 합쳐(merge) Sorted 된 배열을 만들자" 가 이 알고리즘의 아이디어이다. 재귀라고 해서 따라 들어가지 않고, 바로 알 수 있도록 증명해보는 연습을 하는 것이다. Recursive MergeSort int sort(int a[], int n){ if(n

2022.09.12