[정렬] 합병 정렬 (Merge Sort) - 개념, 시간복잡도, 구현

합병 정렬 개념

배열을 절반으로 나누어 각각을 정렬한 후, 합친다.

합병 정렬의 시간복잡도

재귀적으로 구해야 한다.

1. 왼쪽 합병정렬 = T(n/2)

2. 오른쪽 합병정렬 = T(n/2)

3. 합친다  = O(n)

* T(n) = n개의 숫자를 합병정렬할 때의 시간복잡도

* T(n) = 2 x T(n/2) + O(n)  // 점화식

        = 2(2T(n/4) + O(n/2)) + O(n)

        = 4T(n/4) + 2O(n) // 1번 대입

        = 4(2T(n/8) + O(n/4)) + 2O(n)

        = 8T(n/8) + 3O(n) // 2번 대입

        ...... // k번 대입 k+1 = log n

        = n x T(1) + log n x O(n)

        = n x O(1) + O(n log n)

        = O(n) + O(n log n)

* 

합병 정렬 구현 코드

import java.util.Scanner;

public class SortMerge {
	// 합병정렬 : 배열을 절반으로 나누어 각각을 정렬한 후, 합침
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] data = new int [100];
		
		for(int i=0; i<n; i++){
			data[i] = sc.nextInt();
		}		
		mergeSort(data, 0, n-1);
		
		for(int i=0; i<n; i++){
			System.out.print(data[i]+" ");
		}
	}

	// data의 start부터 end까지를 합병정렬하는 함수
	private static void mergeSort(int[] data, int start, int end) {
		if(start >= end) // 숫자가 한 개 남았을 때
			return;
		else{
			int mid = (start+end)/2;
			mergeSort(data, start, mid); // 1. 왼쪽 절반 합병정렬
			mergeSort(data, mid+1, end); // 2. 오른쪽 절반 합병정렬
			merging(data, start, mid, mid+1, end);// 3. 둘을 합침
		}
	}

	// 정렬된 반쪽들을 정렬해서 하나로 합치는 함수
	private static void merging(int[] data, int s1, int e1, int s2, int e2) {
		int p, q; // 현재 최솟값을 가리키는 변수들
		int [] temp = new int[100]; // 합쳐진 결과를 저장하는 임시배열
		int tempIndex = 0;
		
		p = s1; // 왼쪽 절반의 시작점
		q = s2; // 오른쪽 절반의 시작점
		
		while(p <= e1 && q <= e2) {
			if(data[p] <= data[q]){
				temp[tempIndex++] = data[p];
				p++;
			}
			else{
				temp[tempIndex++] = data[q];
				q++;
			}			
		}
		if(p > e1){// q에 남은 숫자가 있는 경우
			for(int i=q; i<=e2; i++){
				temp[tempIndex++] = data[i];
			}
		}
		else{// p에 남은 숫자가 있는 경우
			for(int i=p; i<=e1; i++){
				temp[tempIndex++] = data[i];
			}
		}
		
		// temp[] 완성이 되었으니 data[]에 복사
		for(int i=s1; i<=e2; i++){
			data[i] = temp[i-s1]; //data[] 는 0부터 시작하는 것이 아님, temp는 0부터 시작
		}
	}
}