병합 정렬(Merge Sort)

병합 정렬(Merge Sort)

정렬된 여러 집합을 결합하여 하나의 정렬된 집합으로 만드는 방법.

전체 원소를 부분집합으로 분할하고 각 부분집합에 대해 정렬 작업을 한 뒤 다시 결합한다.

2개의 정렬된 부분집합을 결합하여 하나의 집합으로 만드는 방법을 2-way 병합 정렬이라 하고 n개의 정렬된 부분집합을 결합하여 하나의 집합으로 만드는 방법을 n-way 병합 정렬이라 한다.

​

시간 복잡도는 O(nlog2n)이다.

​

2-way 병합 정렬 예시)

{57, 16, 41, 2, 50, 6, 32, 27}

​

1. 정렬할 집합에 대해서 원소가 하나씩 남을 때까지 분할한다.

{57} {16} {41} {2} {50} {6} {32} {27}

​

2. 부분집합 2개를 정렬하면서 병합한다. 8개의 부분집합이 1개가 될 때까지 반복한 후 종료한다.

{57} {16} {41} {2} {50} {6} {32} {27}

===>

{16, 57} {2, 41} {6, 50} {27, 32}

===>

{2, 16, 41, 57} {6, 27, 32, 50}

===>

{2, 6, 16, 27, 32, 41, 50, 57}

​

프로그램 작성)

package test;

class Sort {
	private int[] sorted = new int[10];
	
	public void mergeSort(int[] a, int m, int n) {
		int middle;
		
		if(m < n) {
			middle = (m + n) / 2;
			mergeSort(a, m, middle);
			mergeSort(a, middle+1, n);
			merge(a, m, middle, n);
		}
	}
	
	public void merge(int a[], int m, int middle, int n) {
		int size = a.length;
		int i, j, k, t;
		i = m;
		j = middle + 1;
		k = m;
		
		while(i <= middle && j <= n) {
			if(a[i] <= a[j]) {
				sorted[k] = a[i++];
			} else {
				sorted[k] = a[j++];
			}
			k++;
		}
		
		if(i > middle) {
			for(t=j; t<=n; t++, k++) {
				sorted[k] = a[t];
			}
		} else {
			for(t=i; t<=middle; t++, k++) {
				sorted[k] = a[t];
			}
		}
		
		for(t=m; t<=n; t++) {
			a[t] = sorted[t];
		}
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6, 32, 27};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.mergeSort(a, 0, a.length-1);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)