[Algorithm] 정렬 - 합병 정렬(Merge sort)

안녕하세요. J4J입니다.

 

이번 포스팅은 정렬 알고리즘 중 합병 정렬에 대해 적어보는 시간을 가져보려고 합니다.

 

 

합병 정렬이란?

 

합병 정렬은 분할 정복법(Divide and Conquer)이 사용되는 정렬 방법으로 저장되어 있는 값들을 모두 분할시킨 뒤 정복을 통해 결합할 때 값들을 정렬해주는 방식을 사용합니다.

 

예를 들어 길이가 5인 배열이 있다고 가정하면 정렬되는 방식은 다음과 같습니다. (길이가 같은 값은 `를 추가시켜 구분합니다.)

 

1-1. 길이가 5인 배열을 반으로 나누어 길이가 3, 2인 배열로 분할 시킵니다.

 

2-1. 길이가 3이 된 배열을 반으로 나누어 길이가 2`, 1인 배열로 분할시킵니다.

2-2. 길이가 2가 된 배열을 반으로 나누어 길이가 1`, 1``인 배열로 분할시킵니다.

 

3-1. 길이가 2`가 된 배열을 반으로 나누어 길이가 1```, 1````인 배열로 분할시킵니다.

3-2. 길이가 1이 된 배열들은 더 이상 분할시키지 않습니다.

 

4-1. 길이가 1```이고 1````인 배열의 값들을 비교하여 정렬하며 길이가 2``인 배열로 합칩니다. (분할된 역순으로 합침)

 

5-1. 길이가 2``이고 1인 배열의 값들을 비교하여 정렬하며 길이가 3`인 배열로 합칩니다.

5-2. 길이가 1`이고 1``인 배열의 값들을 비교하여 정렬하며 길이가 2```인 배열로 합칩니다.

 

6-1. 길이가 3`이고 2```인 배열의 값들을 비교하여 정렬하며 길이가 5`인 배열로 합칩니다.

 

 

구현 코드 (Java)

 

package sorting;

import java.util.Arrays;

public class MergeSort {
	public static void main(String[] args) {
		int intArray[] = new int[]{7, 3, 15, 11, 1};
		
		mergeSort(0, intArray.length-1, intArray); // 합병 정렬
		
		System.out.println(Arrays.toString(intArray)); // [1, 3, 7, 11, 15]
	}
	
	public static void mergeSort(int leftIndex, int rightIndex, int[] array) {
		if(leftIndex >= rightIndex) { // 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같다면 정렬 종료
			return;
		}
		
		int midIndex = (leftIndex + rightIndex)/2;
		
		mergeSort(leftIndex, midIndex, array); // 왼쪽 인덱스부터 중앙 인덱스까지 나누기
		mergeSort(midIndex+1, rightIndex, array); // 중앙 인덱스부터 오른쪽 인덱스까지 나누기
		merging(leftIndex, midIndex, rightIndex, array); // 중앙 인덱스를 기준으로 왼쪽과 오른쪽을 비교하여 정렬하기 
	}
	
	public static void merging(int leftIndex, int midIndex, int rightIndex, int[] array) {
		int temp[] = new int[rightIndex-leftIndex+1]; // 임시로 저장해 둘 배열, 배열의 크기는 leftIndex부터 rightIndex까지
		int tempIndex = 0; // 임시 배열의 인덱스 위치
		int p = leftIndex; // 좌측 배열의 인덱스 위치
		int q = midIndex + 1; // 우측 배열의 인덱스 위치
		
		while(p <= midIndex && q <= rightIndex) { // 좌측 배열과 우측 배열의 인덱스 위치가 끝에 도달하는게 있을 때 까지 반복
			if(array[p] > array[q]) { // 우측 배열이 작을 경우
				temp[tempIndex++] = array[q++]; // 우측 배열의 값을 임시 배열에 저장
			} else { // 좌측 배열이 작을 경우
				temp[tempIndex++] = array[p++]; // 좌측 배열의 값을 임시 배열에 저장
			}
		}
		
		while(p <= midIndex) { // 남은 좌측 배열 값 모두 저장 
			temp[tempIndex++] = array[p++];
		}
		
		while(q <= rightIndex) { // 남은 우측 배열 값 모두 저장
			temp[tempIndex++] = array[q++];
		}
		
		for(int i=leftIndex; i<=rightIndex; i++) { // 임시 배열에 저장된 값을 기존 배열에 재 배치
			array[i] = temp[i - leftIndex];
		}
	}
}

 

합병 정렬 순서

 

728x90

 

특징

 

• 재귀 함수에 대한 이해가 필요하는 등의 이유로 구현이 어려운 편
• 안정 정렬(stable sort)입니다. (정렬 전과 후를 비교했을 때 동일 값들끼리 순서가 변경되지 않습니다.)
• 제자리 정렬(in-place-sort)이 아닙니다. (임시 값을 저장하기 위한 추가적인 공간 사용)
• 분할시킨 뒤 정복(결합 + 복사) 하는 분할 정복법(Divide and Conquer)을 사용합니다.
• 분할할 때 원소의 개수를 균등하게 분할시킵니다.
• 시간 복잡도가 O(NlogN)

 

시간 복잡도가 O(NlogN)인 이유는 분할할 때 logN만큼의 시간이 소비되고 정복할 때 N만큼의 시간이 소비되므로 N x logN인 O(NlogN)이 됩니다.

 

 

정리

 

● 합병 정렬은 값들을 분할시킨 뒤 정복을 통해 정렬하는 방식

● O(NlogN)의 빠른 시간 복잡도를 자랑함

● 빠른 시간 복잡도라는 장점을 가지고 있음

● 구현하기 복잡하다는 단점을 가짐

● 시간을 고려하여 구현해야 될 때 많이 사용되는 정렬 방식에 속함

 

 

 

이상으로 합병 정렬에 대해 간단하게 알아보는 시간이었습니다.