[알고리즘 구현] MergeSort

Alg 동작 원리

Divide and Conquer 방식의 알고리즘으로 말 그대로 나눠서 합친다.

특히 merge 소트는 어렵게 나누고 쉽게 합치는 quick소트와 반대로, 단순하게 나누고 어렵게 합치는 과정을 가진다.
일단 배열을 절반씩 나눈다. 나누다가 배열의 크기가 1씩 남으면 그때부터 mergeAlg를 통해 합치기 시작한다.
merge알고리즘은 배열을 두개씩 잡아서(mergeSort를 두번씩 하기때문에 나눌때 이미 짝이 지어져있다. ) 맨 앞의 방부터 하나씩 비교한다.
(*mid를 기준으로 두개로 나눈 A와 B팀이라고 생각하면 쉽다. 두 팀이 가위바위보를 하는데 이기는 쪽은 계속 대결을 하고 지면 탈락하는 그런 게임을 생각하자. 둘 중 작은것이 져서 배열에 추가되며 탈락되고 이기는 큰 숫자는 계속 대결을 한다.)

계속 합치다가 마지막으로 전체 배열의 중앙을 기준으로 양쪽을 합치면, sorting이 종료된다.
종료조건은 m-n<1 이므로 방이 하나인 배열로 모두 쪼개졌을 때 종료가 된다.

mergeAlg의 정확성은 또 재귀적으로 증명할 수 있다. 제일 큰걸 빼고 소팅해도 결과가 같게 나온다. 이걸 이용한다.

시간복잡도: T(n) = 2T(n/2)+n 이므로 O(nlong n)]

코드(Java)

import java.util.Arrays;

public class mergeAlg {

	public static void main(String[] args) {
		int[] data = { 58, 8, 28, 3, 18, 6, 33, 20 };
		mergeSort(data, 0, data.length - 1);
		System.out.println(Arrays.toString(data));
	}

	public static void merge(int[] data, int n, int m, int mid) {
		int a = n;               // 왼쪽 시작 
		int b = mid+1;           // 오른쪽 시작 
		int[] c = new int[m - n + 1]; // 정렬결과를 담기위한 배열 
		int count = 0;                // c배열에 저장된 개수 
		
		while (a <= mid && b <= m) {
			if (data[a] > data[b]) {
				c[count++] = data[b++];
			} else if (data[a] < data[b]) {
				c[count++] = data[a++];
			} else {
				c[count++] = data[a++];
				c[count++] = data[b++];
			}
		}
		while (a <= mid) {
			c[count++] = data[a++];
		}
		while (b <= m) {
			c[count++] = data[b++];
		}
		for (int i = n; i <= m; i++) {
			data[i] = c[i - n];
		}
	}

	public static void mergeSort(int[] data, int n, int m) {
		if (m - n < 1) 
			return;

		int mid = ((n + m+1) / 2)-1;
		mergeSort(data, n, mid);
		mergeSort(data, mid + 1, m);
		merge(data, n, m, mid);
	}
}

코드(C++)

void merge(int left, int right, int mid){
    int _left = left;
    int _right = mid+1;
    int temp[MAX];
    int count = 0;
    while(_left <= mid && _right<=right){
        if(arr[_left] > arr[_right])
            temp[count++] = arr[_right++];
        else if(arr[_left] < arr[_right])
            temp[count++] = arr[_left++];
        else{
            temp[count++] = arr[_left++];
            temp[count++] = arr[_right++];
        }
    }
    while(_left<= mid)
        temp[count++] = arr[_left++];
    while(_right<= right)
        temp[count++] = arr[_right++];
    for(int i=left;i<=right;i++){
        arr[i] = temp[i-left];
    }
    
}
void mergeSort(int left, int right){
    if(right-left < 1) return;
    int mid = (left+right)/2;
    mergeSort(left, mid);
    mergeSort(mid+1, right);
    merge(left, right, mid);
}