[do it 알고리즘] 병합 정렬

원리

• 분할 정복 방식을 이용하여 하나의 리스트를 두 개의 리스트로 분할
• 각각의 분할된 리스트를 정렬한 후에 합해서 정렬된 하나의 리스트로 만듦

코드

public class MergeSort{
    public static int[] sorted;
    public static void main(String[] args) {
        int[] arr = new int[] {4,2,5,1,3,7,8,9};
        sorted = new int[arr.length];
        mergeSort(arr,0,arr.length-1);

        for(int data : arr){
            System.out.println(data);
        }
    }
    public static void merge(int[] arr,int first,int middle,int last){
        int index1 = first; // 중간을 기준으로 나눠진 첫번째 배열의 첫 index
        int index2 = middle+1; // 중간을 기준으로 나눠진 두번째 배열의 첫 index
        int k = first; // 전역 변수 배열 index

        while(index1 <= middle && index2 <= last){ // 둘 중 한 배열이 다 복사될때까지
            if(arr[index1] > arr[index2]){
                sorted[k] = arr[index2]; // 오름차순 기준
                index2++;
            }else{
                sorted[k] = arr[index1]; // 오름차순 기준
                index1++;
            }
            k++; // 전역 변수 배열 index++;
        }
        if (index1 > middle) { // 첫번째 배열이 다 복사됐으면
            for(int i = index2; i <= last;i++){ // 두번째 배열의 나머지 값 다 복사
                sorted[k] = arr[i];
                k++;
            }
        }else{ // 두번째 배열이 다 복사됐으면
            for(int i = index1; i <= middle;i++){  // 첫번째 배열의 나머지 값 다 복사
                sorted[k] = arr[i];
                k++;
            }
        }
        for(int i = first; i <= last;i++){
            arr[i] = sorted[i]; // 정렬된 배열을 복사해주기
        }
    }
    public static void mergeSort(int[] arr,int first,int last){
        if(first < last) { // 재귀 함수 탈출 조건 : 배열이 길이 1보다 클때만
            int middle = (first + last) / 2;
            mergeSort(arr, first, middle); // first ~ 중간값
            mergeSort(arr, middle + 1, last); // 중간값+1 ~ last
            merge(arr, first, middle, last); // 합치기
        }
    }
}

특징

• 퀵 정렬과 달리 최악의 경우에도 O(NlogN)을 보장
• 임시 배열이 필요하므로 추가 공간이 필요
• 데이터의 크기가 크면 이동 횟수가 많으므로 시간 낭비
• 제자리 상호 교대(swap) 방식이 아님

★코테 단골★