정렬 알고리즘 - 합병 정렬 (Merge Sort)

 

 

합병 정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬하는 작업을 반복하는 알고리즘이다.

n개를 log n번 돌리기 때문에 최선, 평균, 최악 모두 O(n log n)의 시간복잡도를 가진다.

 

 

 

1) 배열을 반으로 나눈다.

2) 각 파티션이 두 개의 요소를 가질 때 까지 계속 반으로 나눠준다.

3) 두 개의 요소를 비교하여 더 작은 요소가 앞으로 오도록 한다.

4) 두 개의 파티션을 비교하여 더 작은 요소가 앞으로 오도록 병합한다.

5) 4 반복

 

 

private static void mergeSort(int[] arr){
    int[] temp = new int[arr.length];
    mergeSort(arr, temp, 0, arr.length - 1);
}
 
public static void mergeSort(int[] arr, int[] temp, int start, int end){
    if (start < end){
        int mid = (start + end)/2;
        mergeSort(arr, temp, start, mid); //앞부분
        mergeSort(arr, temp, mid + 1, end); //뒷부분
        merge(arr, temp, start, mid, end); //병합
    }
}
 
private static void merge(int[] arr, int[] temp, int start, int mid, int end){
    for(int i=start; i<=end; i++){
        tmep[i] = arr[i];
    }
    
    int part1 = start;
    int part2 = mid + 1;
    int index = start; //다음 저장할 곳
 
    while (part<=mid && part2<=end){
        if(temp[part1] <= temp[part2]){
            arr[index] = temp[part1];
            part1++;
        }
        else {
            arr[index] = temp[part2];
            part2++;
        }
        index++;
    }
 
    //뒤쪽 배열은 모두 비웠는데 앞쪽 배열은 남아있을 경우
    for(int i=0; i<=mid-part1; i++){
        arr[index+i] = temp[part1+i];
    }
 
    //앞쪽 배열은 비어있고 뒤쪽 배열만 남은건
    //최종 배열에 이미 뒤쪽 배열 데이터가 있기 때문에 신경X
}

 

합병 정렬은 정렬 과정에서 별도의 저장 공간을 필요로 하기 때문에

공간이 없을 경우 퀵소트를 사용함! (퀵소트도 평균 O(n log n))

 

안정된 정렬.