[Sort] Merge

youtu.be/2YvFRAC8UTM

https://www.youtube.com/watch?v=QAyl79dCO_k

 

- Merge Sort

- Quick Sort 

 

 분할정복법을 사용

 

- 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할

- 정복 : 각각의 작은 문제를 순환적으로 해결

- 합병 : 작은 문제의 해를 합하여(merge) 원래 문제에 대한 해를 구함

 

O(n log n)

 

 

숫자를 보며 소트 순서를 이해하자

 

package algorithm.sort;

public class Merge {

    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;
//            System.out.println("mid : " + mid);
            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++];
            }else{
                arr[index++] = tmp[part2++];
            }
        }

        // Flush all
        while(part1 <= mid){
            arr[index++] = tmp[part1++];
        }
        while(part2 <= end){
            tmp[index++] = arr[part2++];
        }

//        printArr(arr);

    }

    private static void printArr(int[] arr){

        for(int i = 0 ; i < arr.length ; i++){
            if(i != 0) System.out.print(" -> ");
            System.out.print(arr[i]);
        }
        System.out.println();

    }

    public static void main(String[] args) {


//        int[] arr = {3,6,1,9,2,   7,4,8,5,0,   14,23,98,45,76,   34};
        int[] arr = {5,3,4,1,2};

        mergeSort(arr);

        printArr(arr);

    }

}