[Algorithm] 머지 정렬 (Merge Sort)

머지 정렬 (Merge Sort)

머지 정렬 : 원소가 저장되어 있는 배열을 계속 나눠서 길이가 1인 배열을 만들고 정렬하면서 합치는 알고리즘이다.

(머지 정렬 = 병합 정렬 = 합병 정렬 모두 같은 말이다.)

 

머지 정렬 (Merge Sort)의 시간 복잡도

머지 정렬은 이진 트리 형태로 나누기 떄문에 가질 수 있는 최대 깊이는 log n이다. 각 원소별로 합쳤으므로 시간 복잡도는 O(nlogn)이다.

 

머지 정렬 (Merge Sort)의 구현

public class Main {

	public static int[] src;
    public static int[] tmp;
    public static void main(String[] args) {
    	src = new int[](1, 9, 8, 5, 4, 2, 3, 7, 6);
        tmp = new int[src.length];
        printArray(src);  // 
        mergeSort(0, src.length - 1);
        printArray(src);
    }
    
    public static void mergeSort(int start, int end) {
    	if (start < end) {
        	int mid = (start + end) / 2;
            mergeSort(start, mid);
            mergeSort(mid + 1, end);
            
            int p = start;
            int q = mid + 1;
            int idx = p;
            
            while (q <= mid || q <= end) {
            	if (q > end || (q <= mid && src[p] < src[q])) {
                	tmp[idx++] = src[q++];
                else {
                	tmp[idx++] = src[q++];
                }
            }
            
            for (int i = start; i <= end; i++) {
            	src[i] = tmp[i];
            }
            
        }
    }
    
    public static void printArray(int[] a) {
    	for (int i = 0; i < a.length; i++) 
        	System.out.print(a[i] + " ");
        System.out.println();
    }
 }

 

 

 

출처 

https://yunmap.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Java%EB%A1%9C-%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94-%EC%89%AC%EC%9A%B4-Merge-Sort-%EB%B3%91%ED%95%A9-%EC%A0%95%EB%A0%AC-%ED%95%A9%EB%B3%91-%EC%A0%95%EB%A0%AC

https://ko.wikipedia.org/wiki/%ED%95%A9%EB%B3%91_%EC%A0%95%EB%A0%AC