[자료구조/Java] 병합정렬(Merge Sort)

 

youtu.be/QAyl79dCO_k

 

1. 파티션이 낱개가 될 때까지 배열을 반으로 쪼갠다.

 

2. 두 배열을 잡아 작은 수부터 비교하고, 작은 것을 먼저 넣는다.

정렬이 완료되면 원래 배열의 자리에 복사한다.

 

3. (2의 반복) 정렬된 작은 배열을 병합한다.

과정) 각 배열의 가장 작은 수부터 비교하고 작은 것을 먼저 넣는다.

 

n개만큼씩 logn번 돌기 때문에 시간복잡도는 O(nlogn)

n번 호출, 1번 호출 당 검색해야 하는 데이터의 개수가 절반씩 줄어드니까 logn

 

 

 Merge Sort 는 실행시에 별도의 저장공간을 필요로 하기 때문에, 저장공간이 없다면 Quick Sort를 사용한다.

 

코드

public class Test{
	private static void mergeSort(int[] arr){
    	int tmp[] = new int[arr.length];
    	mergeSort(arr, tmp, 0, arr.length-1);
    }
    private static void mergeSort(int[] arr, int[] tmp, int start, int end){
    	if(start < end){
        	int mid = (start + end)/2;
            mergeSort(arr, tmp, start, mid);
            mergeSort(arr, tmp, mid+1, end);
            merge(arr, tmp, start, mid, end);
        }
    }
    private static void merge(int[] arr, int[] tmp, int start, int mid, int end){
    	for(int i=start; i<=end; i++){
       		tmp[i] = arr[i];
        }
        //두 배열의 시작점
        int part1 = start;
        int part2 = mid+1;
        //결과 배열의 시작점
        int index = start;
        
        while(part1 <= mid && part2 <= end){
        	if(tmp[part1] <= tmp[part2]){
            	arr[index] = tmp[part1];
                part1++;
            }else{
            	arr[index] = tmp[part2];
                part2++;
            }
            index++;
        }
        //뒤쪽 배열은 비었고 앞쪽 배열에 남아 있는 경우
        //앞쪽 포인터가 배열의 끝에서 남은 만큼까지를 넣어줌
        for(int i=0; i < mid-part1; i++){
        	arr[index+i] = tmp[part1+i];
        }
        //뒤쪽 배열이 남아 있는 경우, 최종 배열에 이미 데이터가 남아 있기 때문에 신경쓰지 않아도 된다.
    }
    private static void printArray(int[] arr){
    	for(int data : arr){
        	System.out.print(data + ", ");
        }
        System.out.println();
    }
    public static void main(String[] args){
    	int[] arr = {3, 9, 4, 7, 5, 0, 1, 6, 8, 2};
        printArray(arr);
        mergeSort(arr);
        printArray(arr);
    }
}