[JAVA] 병합정렬,합병정렬(Merge Sort)

병합정렬, 합병정렬(Merge Sort)

분할정복(divide-and-conquer)의 한 종류인 합병정렬에 대해 알아보겠습니다.

컨셉은 리스트를 두개로 나누고 각 하위 리스트를 정렬 후 하나로 합치는 방법입니다.

설명보다 그림을 보는게 이해가 더 빠를 듯 싶어서 이해가 쉽게될 만한 그림을 가져왔습니다.

(그림 출처 : http://blog.naver.com/k97b1114/140163896337)

병합 정렬의 성능은 O(nlogn)이고 각각의 병합시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생합니다.

package sort;
 
import java.util.ArrayList;
import java.util.List;
 
public class MergeSort {
    public List<Integer> mergeSort(final List<Integer> input){
        if(input.size() < 2)
            return input;
        
        final List<Integer> leftHalf = input.subList(0, input.size()/2); // 왼쪽 절반 
        final List<Integer> rightHalf = input.subList(input.size()/2, input.size()); // 오른쪽 절반 
        
        return merge(mergeSort(leftHalf), mergeSort(rightHalf));
    }
    
    // 병합 
    private List<Integer> merge(final List<Integer> left, final List<Integer> right){
        int leftPtr = 0;
        int rightPtr = 0;
        
        final List<Integer> mergedList = new ArrayList<>(left.size() + right.size());
        
        while(leftPtr < left.size() && rightPtr < right.size()) {
            if(left.get(leftPtr) < right.get(rightPtr)) {
                mergedList.add(left.get(leftPtr));
                leftPtr++;
            }else {
                mergedList.add(right.get(rightPtr));
                rightPtr++;
            }
        }
        // 나머지 데이터 삽입
        while(leftPtr < left.size()) {
            mergedList.add(left.get(leftPtr));
            leftPtr++;
        }
        
        while(rightPtr < right.size()) {
            mergedList.add(right.get(rightPtr));
            rightPtr++;
        }
        
        return mergedList;
    }
}
 

* merge() 메서드는 정렬된 두개의 list를 병합하며 정렬하는 기능을 갖고있습니다.

Junit Test Code

public class Sort {
 
    @Test
    public void mergeSort() {
        MergeSort sort = new MergeSort();
        List<Integer> input = Arrays.asList(5,10,2,8,9,3,1,7,4,6);
        List<Integer> output = sort.mergeSort(input);
        
        List<Integer> result = Arrays.asList(1,2,3,4,5,6,7,8,9,10);
        
        assertArrayEquals(output.toArray(), result.toArray());
    }
 
}

그린라이트!