정렬5) 병합 정렬(Merge Sort)

* 병합 정렬(합병 정렬, 머지 소트)
    - 주어진 배열을 '임시 저장 공간'에 모두 분리 후 합치는 방식


* 병합 정렬 로직
    0.1 원본 배열
    
    0.2 임시 배열
    

    1. 배열의 크기가 1이 될 때 까지 계속 반으로 나누기
    

    2. 인접한 값을 임시 배열에 넣기
    

    3. 임시 배열에서 정렬하며 길이 2인 배열로 합쳐주기
    

    4. 길이 2인 인접한 값을 임시 배열에 넣기
    

    5. 임시 배열에서 정렬하여 길이 4인 배열로 합쳐주기
    

    

    

    

    6. 위 과정 반복


* 시간 복잡도
    - 최선, 최악 둘 다 O(nlogn)