Merge sort Java 코드

Merge sort

전체를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하며 정렬하는 방식

시간복잡도

n*log2(n)

공간복잡도(이 코드의 경우)

n

Java 코드

public class MergeSort {
    int[] arr; //입력 받는 배열
    int[] temp; //합칠때 사용 하는 임시 배열
    
    //배열에 입력 받기
    public MergeSort(int[] _arr){
        arr = _arr;
        temp = new int[arr.length];
    }
    
    //low~mid, mid+1~high 정렬 후 병합
    public void mergeSort(int low, int high){
        if(low >= high) return;
        int mid = (low + high) / 2;
        mergeSort(low, mid);
        mergeSort(mid+1, high);
        merge(low, mid, high);
    }
    
    //low~mid, mid+1~high 두 구간을 병합
    public void merge(int low, int mid, int high){
        //low~high 구간을 temp 배열에 저장
        for(int i=low; i<=high; i++){
            temp[i] = arr[i];
        }
        //low~mid, mid+1~high 두 구간의 값들을 각각 비교해가며 작은값 부터 원래 배열에 저장
        int curIndex = low;
        int lowIndex = low;
        int highIndex = mid+1;
        while(lowIndex <= mid && highIndex <= high){
            if(temp[lowIndex] <= temp[highIndex]) arr[curIndex++] = temp[lowIndex++];
            else arr[curIndex++] = temp[highIndex++];
        }
        //왼쪽 구간이 남았을 경우 마저 저장
        //오른쪽 구간은 이미 정렬된 상태로 저장되 있기 때문에 따로 처리할 필요 없음
        while(lowIndex <= mid) arr[curIndex++] = temp[lowIndex++];
    }
    
    //배열 출력
    public void printArr(){
        System.out.println(Arrays.toString(arr));
    }
}