합병정렬(Merge sort)_개념/시간복잡도/Stable/Not In-place
합병 정렬에 대한 이해 - 합병정렬이란, 하나의 배열을 두개의 균등한 배열로 분할하고 분할된 배열을 각각 정렬한 다음, 이를 다시 합하여 정렬을 완성하는 알고리즘이다. - 합병정렬은 분할 정복의 일종으로, 하나의 큰 문제를 두개의 작은 문제로 분할하여 해결한 다음, 결과를 모아서 문제를 완전히 해결하는 전략이다. 코드를 먼저 살펴보면, void mergeSort(int st, int en) { if (en == st+1) return ; int mid = (st+en)/2; mergeSort(st, mid); //arr[st:en]을 두개의 균등한 배열로 분할하여 각각 정렬 mergeSort(mid, en); merge(st, en); //정렬된 두개의 배열 arr[st:mid], arr[mid:en]을..
2022. 2. 19.