10989

수 정렬하기 3 : https://www.acmicpc.net/problem/10989

 

merge sort로 무난하게 AC

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static int N;
	static boolean DBG = false;
	static int[] sorted;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		sorted = new int[N];
		for (int i = 0; i < N; i++)
			arr[i] = Integer.parseInt(br.readLine());

		merge_sort(arr, 0, N - 1);

		StringBuilder sb = new StringBuilder();
		for (int v : arr) {
			sb.append(v).append('\n');
		}
		System.out.println(sb);

	}

	private static void merge_sort(int[] list, int left, int right) {
		if (left < right) {
			int mid = (left + right) / 2;
			merge_sort(list, left, mid);
			merge_sort(list, mid + 1, right);
			merge(list, left, right, mid);
		}

	}

	private static void merge(int[] list, int left, int right, int mid) {
		int i, j, k, l;
		// list index
		i = left;
		j = mid + 1;
		// sorted index
		k = left;

		while (i <= mid && j <= right) {
			if (list[i] <= list[j]) {
				sorted[k++] = list[i++];
			} else {
				sorted[k++] = list[j++];
			}
		}
		if(DBG)
		System.out.printf("%d %d %d\n",i , j ,k);
		if (i > mid) {
			while (j <= right) {
				sorted[k++] = list[j++];
			}
		} else {
			while (i <= mid)
				sorted[k++] = list[i++];
		}

		for (l = left; l <= right; l++)
			list[l] = sorted[l];

	}

}