[알고리즘] JAVA 병합 정렬 (Merge Sort) 알고리즘

  

 

- 분할 정복 방법으로, 퀵정렬과 다르게 항상 시간 복잡도가 O(N*logN)을 보장 

- 일단 반으로 나누고 나중에 합친다. → 피벗이 없는 이유 : 항상 반으로 나누기 때문

- 합치는 순간에 정렬

- 기존의 데이터를 담을 추가적인 배열 공간이 필요 → 메모리 낭비

 

문제 

- 5, 3, 2, 6, 4, 7, 8, 1을 오름차순으로 나타내시오.

- 정렬배열은 반드시 전역변수로 선언

 

소스 코드

package _38_midian;

import java.util.Arrays;


public class MergeSort {
    static int[] sorted = new int[8];
    public static void merge(int a[], int m, int middle, int n) {
        int i = m;             // 첫 번째 부분집합의 시작 위치 설정
        int j = middle+1;     // 두 번째 부분집합의 시작 위치 설정
        int k = m;             // 배열 sorted에 정렬된 원소를 저장할 위치 설정
        
        while(i<=middle && j<=n) {
            if(a[i]<=a[j]) {
                sorted[k] = a[i];
                i++;
            }else {
                sorted[k] = a[j];
                j++;
            }
            k++;
        }
        if(i>middle) {
            for(int t=j;t<=n;t++,k++) {
                sorted[k] = a[t];
            }
        }else {
            for(int t=i;t<=middle;t++,k++) {
                sorted[k] = a[t];
            }
        }
        
        for(int t=m;t<=n;t++) {
            a[t] = sorted[t];
        }
    }
        
    
    public static 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 static void main(String[] args) {
        int[] list = {5, 3, 2, 6, 4, 7, 8, 1};
        int size = list.length;
        mergeSort(list, 0, size-1);
        for(int i=0; i<size; i++) {
        	System.out.print(list[i] + " ");
        }
      
    }
 
}

 

출력 결과