분할 정복 알고리즘 개요
배열 정렬을 위해 널리 사용되는 합병 정렬은 분할 정복(Divide and Conquer) 패러다임을 기반으로 합니다. 이 방식은 주어진 데이터를 작은 단위로 재귀적으로 쪼갠 후, 각 단위를 정렬된 상태로 다시 결합하여 전체 순서를 맞춥니다.
단계 1: 데이터 분할 로직
먼저 배열을 두 개의 하위 부분으로 나누는 과정을 정의합니다. 이때 중간 지점을 기준으로 왼쪽과 오른쪽 구간을 각각 소팅해야 합니다. 임시 버퍼 메모리를 활용하여 추가적인 공간 복잡도를 희생하되 시간 성능을 보장합니다.
// 최상위 진입점
public static void initiateSort(int[] targetData) {
if (targetData == null || targetData.length <= 1) return;
int[] auxiliary = new int[targetData.length];
splitAndConquer(targetData, 0, targetData.length - 1, auxiliary);
}
// 재귀적 분할 함수
private static void splitAndConquer(int[] source, int low, int high, int[] auxBuffer) {
if (low < high) {
int middle = low + (high - low) / 2; // 오버플로우 방지용 계산
splitAndConquer(source, low, middle, auxBuffer);
splitAndConquer(source, middle + 1, high, auxBuffer);
unifySegments(source, low, middle, high, auxBuffer);
}
}단계 2: 구간 병합 수행
두 개의 정렬된 서브 배열을 하나로 합칠 때는 두 개의 포인터를 사용합니다. 첫 번째 포인터는 왼쪽 구간의 시작점이고, 두 번째 포인터는 오른쪽 구간의 시작점을 가리킵니다. 두 값 중 더 작은 것을 선택해 임시 배열에 복사한 뒤 포인터를 이동시킵니다.
// 정렬된 두 구간을 하나의 배열로 합치는 함수
private static void unifySegments(int[] mainArr, int start, int mid, int end, int[] tempArr) {
int ptrLeft = start;
int ptrRight = mid + 1;
int bufIndex = 0;
// 양쪽 영역이 모두 남아있는 경우 비교하며 병합
while (ptrLeft <= mid && ptrRight <= end) {
if (mainArr[ptrLeft] <= mainArr[ptrRight]) {
tempArr[bufIndex++] = mainArr[ptrLeft++];
} else {
tempArr[bufIndex++] = mainArr[ptrRight++];
}
}
// 왼쪽에 남은 데이터가 있다면 처리
while (ptrLeft <= mid) {
tempArr[bufIndex++] = mainArr[ptrLeft++];
}
// 오른쪽에 남은 데이터가 있다면 처리
while (ptrRight <= end) {
tempArr[bufIndex++] = mainArr[ptrRight++];
}
// 최종 결과를 원래 배열에 복원
bufIndex = 0;
for (int i = start; i <= end; i++) {
mainArr[i] = tempArr[bufIndex++];
}
}통합 클래스 구조
다음은 위 두 논리가 통합되어 실행되는 전체 소스 코드를 보여줍니다. 테스트 데이터를 생성하고 결과를 출력하는 메인 메서드를 포함하며, 불필요한 글로벌 변수나 중복 로직을 제거하여 유지보수성을 높였습니다.
import java.util.Arrays;
public class ArrayMerger {
public static void main(String[] args) {
int[] dataSet = {9, 4, 7, 2, 1, 8, 5, 3};
System.out.println("정렬 전: " + Arrays.toString(dataSet));
initiateSort(dataSet);
System.out.println("정렬 후: " + Arrays.toString(dataSet));
}
public static void initiateSort(int[] data) {
if (data != null && data.length > 1) {
int[] workspace = new int[data.length];
splitAndConquer(data, 0, data.length - 1, workspace);
}
}
private static void splitAndConquer(int[] src, int left, int right, int[] buffer) {
if (left >= right) return;
int center = left + ((right - left) >> 1);
splitAndConquer(src, left, center, buffer);
splitAndConquer(src, center + 1, right, buffer);
unifySegments(src, left, center, right, buffer);
}
private static void unifySegments(int[] src, int l, int m, int r, int[] buf) {
int idx1 = l;
int idx2 = m + 1;
int k = 0;
while (idx1 <= m && idx2 <= r) {
buf[k++] = (src[idx1] <= src[idx2]) ? src[idx1++] : src[idx2++];
}
while (idx1 <= m) {
buf[k++] = src[idx1++];
}
while (idx2 <= r) {
buf[k++] = src[idx2++];
}
// 원본 배열에 업데이트
for (int i = 0; i < k; i++) {
src[l + i] = buf[i];
}
}
}