Merge sort

Advanced 정렬하기

 

문제

---

서로 다른 n개의 정수가 주어질 때, 이를 1초안에 오름차순으로 정렬하는 프로그램을 작성하시오.  

입력

---

첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.  

출력

---

첫 번째 줄에 n개의 숫자를 합병정렬을 이용하여 오름차순으로 정렬한 결과를 출력한다.

 

예제 입력

10
2 5 3 4 8 7 -1 9 10 2

예제 출력

-1 2 2 3 4 5 7 8 9 10

코드

//merge sort

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static int[] sorted;

    //첫 번째 줄에 n이 주어진다. ( 1 ≤ n ≤ 100,000 ) 두번째 줄에 n개의 정수가 주어진다.
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int[] b;
        int c;
        int d = 0;

        a = sc.nextInt();
        b = new int[a];
        sorted = new int[a];

        for (int i = 0; i < a; i++) {
            b[i] = sc.nextInt();
        }

        mergeSort(b, 0, a - 1);

        sc.close();

        for (int i = 0; i < a; i++) {
            System.out.print(sorted[i] + " ");
        }
    }

    public static void mergeSort(int[] arr, int m, int n) {
        int middle;
        if (m < n) {
            middle = (m + n) / 2;
            mergeSort(arr, m, middle);
            mergeSort(arr, middle + 1, n);
            merge(arr, m, middle, n);
        }
    }

    public static void merge(int[] arr, int m, int middle, int n) {
        int i, j, k, t;

        i = m;
        j = middle + 1;
        k = m;

        while (i <= middle && j <= n) {
            if (arr[i] <= arr[j])
                sorted[k] = arr[i++];
            else
                sorted[k] = arr[j++];
            k++;
        }

        if (i > middle) {
            for (t = j; t <= n; t++, k++)
                sorted[k] = arr[t];
        } else {
            for (t = i; t <= middle; t++, k++)
                sorted[k] = arr[t];
        }

        for (t = m; t <= n; t++)
            arr[t] = sorted[t];

    }


}