[자바] 합병정렬 자바 코드

 

 

 

 

합병 정렬

 

 

 

시간복잡도가 낮은 정렬 방법입니다.

 

합병정렬: O(nLog n)

 

 

아래 그림처럼 최소단위로 분할한뒤 다시 합치는데

합치는 과정에서 정렬을 하게 됩니다.

반복되는 합병 과정에서 정렬된 배열 간 합병만 발생하기 때문에 시간복잡도가 낮습니다.

 

 

 

합병 정렬 자바 코드입니다.

 

//합병정렬
public void mergeSort(int[] arr) {
    if(arr.length > 1) {
        int[] left = new int[arr.length/2];
        int[] right = new int[arr.length - left.length];
 
        for(int i=0;i<left.length;i++)
            left[i] = arr[i];
        for(int i=0;i<right.length;i++)
            right[i] = arr[i+left.length];
 
        mergeSort(left);
        mergeSort(right);
        merge(left, right, arr);
    }else {
        return ;
    }
}
 
//합병
public void merge(int[] left, int[] right, int[] arr) {
    int leftIdx = 0;
    int rightIdx = 0;
    int arrIdx = 0;
 
    while (leftIdx < left.length) {
        if (rightIdx < right.length) {
            if ( left[leftIdx] < right[rightIdx]) {
                arr[arrIdx] = left[leftIdx];
                leftIdx++;
            }else{
                arr[arrIdx] = right[rightIdx];
                rightIdx++;
            }
            arrIdx++;
        }else {
            while (leftIdx < left.length) {
            arr[arrIdx] = left[leftIdx];
            leftIdx++;
            arrIdx++;
            }
        }
    }
 
    while (rightIdx < right.length) {
        arr[arrIdx] = right[rightIdx];
        rightIdx++;
        arrIdx++;
    }
}

 

 

위 코드에서

mergeSort(arr);

 

를 호출하면 인자로 넘긴 배열이 오름차순 정렬됩니다.

 

※다른 얘기지만 자바에서는 기본 자료형을 제외하고 전부 Call By Reference 방식이기 때문에 return 없이 처리 가능합니다.