병합 정렬(Merge Sort)

병합 정렬이란?

• 존 폰 노이만이 제안한 방법
• 분할 정복 알고리즘의 하나

병합 정렬 알고리즘 개념

• 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체 정렬된 리스트가 되게하는 방법

• 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할

• 정복(Conquer) : 부분배열을 정렬한다. 부분 배열의 크기가 크다면 순환 호출을 이용하여 다시 분할 정복을 한다.

• 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병

병합 정렬 과정

 

 

코드

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = { 69, 10, 30, 2, 16, 8, 31, 22};
		mergeSort(arr, 0, arr.length-1);
		
		for(int a : arr) {
			System.out.print(a + " ");
		}
	}
	
	public static void mergeSort(int[] arr, int m, int n) {
		int middle;
		if(m < n) {
			middle = (m + n) / 2;
			mergeSort(arr, m, middle);
			mergeSort(arr, middle+1, n);
			merge(arr, m, middle, n);
		}
	}

	private static void merge(int[] arr, int m, int middle, int n) {
		
		int i = m;
		int j = middle + 1;
		int k = m;
		
		int temp[] = new int[arr.length];
		
		while(i<=middle && j<=n) {
			if(arr[i] < arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}
		}
		
		while(i<=middle) {
			temp[k++] = arr[i++];
		}
		
		while(j<=n) {
			temp[k++] = arr[j++];
		}
		
		for(int l = m; l <= n ; l++) {
			arr[l] = temp[l];
		}
				
	}
}

시간복잡도

참고링크

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://xmfpes.github.io/algorithm-study/daily-algorithm-09/