병합 정렬(Merge Sort)은 배열을 절반씩 나누어 각각 정렬한 뒤 다시 하나로 합치는 분할 정복(Divide and Conquer) 기반의 대표적인 정렬 알고리즘입니다. 아래는 자바(Java)로 작성한 병합 정렬 프로그램입니다.
예제 코드
import java.util.Arrays;
public class Demo{
public static void merge_sort(int[] my_arr){
if(my_arr == null){
return;
}
if(my_arr.length > 1){
int mid = my_arr.length / 2;
int[] left = new int[mid];
for(int i = 0; i < mid; i++){
left[i] = my_arr[i];
}
int[] right = new int[my_arr.length - mid];
for(int i = mid; i < my_arr.length; i++){
right[i - mid] = my_arr[i];
}
merge_sort(left);
merge_sort(right);
int i = 0;
int j = 0;
int k = 0;
while(i < left.length && j < right.length){
if(left[i] < right[j]){
my_arr[k] = left[i];
i++;
} else {
my_arr[k] = right[j];
j++;
}
k++;
}
while(i < left.length){
my_arr[k] = left[i];
i++;
k++;
}
while(j < right.length){
my_arr[k] = right[j];
j++;
k++;
}
}
}
public static void main(String[] args){
int my_arr[] = {56, 78, 91, 21, 34, 0, 11};
int i=0;
merge_sort(my_arr);
System.out.println("The array after sorting is ");
for(i=0; i<my_arr.length; i++)
System.out.print(my_arr[i]+" ");
}
}실행 결과
The array after sorting is 0 11 21 34 56 78 91
코드 동작 원리
Demo라는 이름의 클래스에는 'merge_sort' 함수가 정의되어 있습니다. 이 함수는 먼저 배열이 null인지, 즉 비어 있는지 확인하고 비어 있다면 아무 작업 없이 그대로 반환합니다.
배열의 길이가 1보다 큰 경우에는 중간 지점(mid)을 계산한 뒤 배열을 절반으로 나눕니다. 이때 왼쪽 절반의 요소들은 새로운 left 배열에, 오른쪽 절반의 요소들은 right 배열에 각각 복사됩니다.
나눠진 두 배열은 각각 다시 정렬 과정을 거친 후, 세 개의 인덱스 변수(i, j, k)를 사용해 양쪽 배열의 요소를 순서대로 비교하면서 원래 배열(my_arr)에 병합됩니다. 한쪽 배열의 요소를 모두 소진한 뒤에는 남은 쪽의 요소들을 그대로 뒤에 복사하여 최종적으로 정렬된 배열이 완성됩니다.
main 함수에서는 정렬할 배열을 선언하고 merge_sort 함수를 호출한 다음, 정렬이 완료된 배열의 내용을 콘솔에 출력합니다.
시간 복잡도
병합 정렬은 최선, 평균, 최악의 경우 모두 O(n log n)의 시간 복잡도를 가지므로 입력 데이터의 초기 순서에 거의 영향을 받지 않고 안정적인 성능을 보입니다. 다만 병합 과정에서 추가적인 배열 공간이 필요하기 때문에 공간 복잡도는 O(n)입니다.