[인프런 알고리즘 문제풀이] 병합정렬

문제

인프런 알고리즘 문제풀이

• The copyright in this matter is in Inflearn

입력1

8
7 6 3 1 5 2 4 8

출력1

1 2 3 4 5 6 7 8

풀이

1. [7,6,3,1,5,2,4,8]
2. 반으로 쪼갠 [7,6,3,1][5,2,4,8]
3. 다시 반으로 쪼갠 [7,6][3,1][5,2][4,8]
4. 다시 반으로 쪼갠 [7][6][3][1][5][2][4][8]
5. 더이상 쪼갤 수 없으니 두 쌍씩 결합하면서 두개의 쌍의 처음 원소부터 시작하여 작은 값을
   새로운 tmp배열에 넣는 과정으로 작은 숫자가 앞으로 오름차순 정렬을 시킴.그리고 이 tmp 배열값을
   a 배열에 복사해준다.
6. [6,7][1,3][2,5][4,8]
   7.[1,3,6,7][2,4,5,8]
   8.[1,2,3,4,5,6,7,8]

시간복잡도

분할과정에서는 데이터가 N개면 level(깊이)가 logN만큼 생기고,
각각의 결합과정은 최대 N번 비교를 하니 NlogN.

코드

/* 62. 병합정렬 */
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.StringTokenizer;

class Main
{
    static int[] a;
    static int[] tmp;
    static int n;
    public static void main (String[] args) throws java.lang.Exception
    {
        
        System.setIn(new FileInputStream("input.txt"));
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        n = Integer.parseInt(st.nextToken());
        a = new int[n+1];
        tmp = new int[n+1];
        st = new StringTokenizer(br.readLine());
        for(int i = 1;i<=n;i++){
            a[i] = Integer.parseInt(st.nextToken());
        }

        divide(1,n);

        for(int i = 1;i<=n;i++){
            System.out.print(a[i]);
        }
    }

    static void divide(int lt, int rt){
        int mid;
        int p1,p2,p3;

        if(lt < rt){
            mid = (lt + rt)/2;
            divide(lt,mid);
            divide(mid+1,rt);
            p1 = lt;
            p2 = mid+1;
            p3 = lt;
            while(p1 <= mid && p2 <= rt){
                if(a[p1] > a[p2]){
                    tmp[p3++] = a[p2++];
                }else{
                    tmp[p3++] = a[p1++];
                }
            }

            while(p1 <= mid){
                tmp[p3++] = a[p1++];
            }
            
            while(p2 <= rt){
                tmp[p3++] = a[p2++];
            }

            for(int i = lt;i<=rt;i++){
                a[i] = tmp[i];
            }

        }
    }
}