[Java][알고리즘][정렬] Merge Sort / 합병 정렬

합병 정렬

분할 정복 방식을 이용한 정렬이다. 드디어 성능이 좋아진다! O(NlogN)을 보장해준다.

각 배열을 계속 분할하여 정렬을 시키고 다시 합치면서 다시 정렬을 해준다.

 

Merge에서는 위와 같은 과정이 생긴다. 단점으로는 보조 배열을 만들어야 해서 정렬하고자 하는 배열과 같은 크기의 보조 배열을 만들어줘야 한다.

 

코드

public class Merge {    
    public static boolean isless(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
    
    public static void swap(Comparable[] arr, int i,int j) {
        Comparable p = arr[i];
        arr[i] = arr[j];
        arr[j] = p;
    }
    
    public static void show(Comparable[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void Sort(Comparable[] a) {
        Comparable[] b = new Comparable[a.length];
        Sort(a,b, 0, a.length-1);
    }
    
    public static void Sort(Comparable[] a,Comparable[] b, int low, int high) {
        if(low>=high) return;
        int mid = low + (high-low)/2;
        Sort(a,b,low,mid);
        Sort(a,b,mid+1,high);
        if(!isless(a[mid+1],a[mid])) return;
        Merge(a,b,low,mid,high);
        show(a);
    }
    
    public static void Merge(Comparable[] a,Comparable[] b, int low, int mid, int high ) {
        int i = low;
        int j = mid+1;
        
        for(int k=low; k<=high; k++) {
            if(i>mid) b[k] = a[j++];
            else if(j>high) b[k] = a[i++];
            else if(isless(a[j],a[i])) b[k] = a[j++];
            else b[k] = a[i++];
        }
        
        for(int k=low; k<=high; k++) {
            a[k] = b[k];
        }
    }
}