머지소트란?

머지소트란?

• 배열을 반으로 나눠서 정렬하는 방식

• 재귀적으로 반으로 나눠지고, 합쳐질때 정렬된 상태

• 시간복잡도는 O(NlogN), 공간복잡도는 O(N)이다.

• 함수를 호출하는 공간복잡도는 O(logN)이지만, 배열 크기의 공간복잡도가 O(N)이므로 O(N)

• 안정 정렬

구현 방법?

• 재귀적으로 배열을 반으로 나누는 코드 작성

• 반으로 나눠진 배열을 합쳐서 정렬하는 코드 작성

• 배열을 합칠 때, 나눠진 배열에 대해서 포인터를 이용해 값을 비교하도록 한다.

• 재귀적으로 함수를 호출하므로, 역으로 정렬되면서 최종적으로 모든 원소가 정렬

코드?

class Solution {
    void split(int[] nums, int start, int end){        
        if(start >= end)
            return;
        
        int mid = start + (end - start) / 2;
        
        split(nums, start, mid);
        split(nums, mid + 1, end);
        merge(nums, start, end);
    }
    
    void merge(int[] nums, int start, int end){
        int[] result = new int[end - start + 1];
        
        int mid = start + (end - start) / 2;
        int idx1 = start;
        int idx2 = mid + 1;
        
        int rIdx = 0;
        
        while(idx1 <= mid && idx2 <= end){
            if(nums[idx1] < nums[idx2]){
                result[rIdx] = nums[idx1];
                idx1++;
            }else{
                result[rIdx] = nums[idx2];
                idx2++;
            } 
            rIdx++;
        }        

        if(idx1 > mid){
            while(idx2 <= end){
                result[rIdx] = nums[idx2];
                idx2++;
                rIdx++;
            }
        }
        
        if(idx2 > end){
            while(idx1 <= mid){
                result[rIdx] = nums[idx1];
                idx1++;
                rIdx++;
            }
        }
        
        for(int i = start; i <= end; i++){
            nums[i] = result[i - start];
        }
    }
    
    public int[] sortArray(int[] nums) {
        split(nums, 0, nums.length - 1);
        return nums;
    }
}