[알고리즘] [2] 병합 정렬

import java.util.*;

public class Main {
	static int[] arr;
	static int [] sortedArr;
	static int m;
	static int cnt = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		m = sc.nextInt();
		arr = new int[n];
		sortedArr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
			sortedArr[i] = arr[i];
		}
		mergeSort(0, arr.length - 1);
		
		System.out.println(Arrays.toString(sortedArr));
	}
	
	private static void mergeSort(int stt, int fin) {	
		if (fin > stt) {
			int mid = (stt + fin) / 2;
			mergeSort(stt, mid);
			mergeSort(mid + 1, fin);
			
			int i = stt;
			int j = mid + 1;
			int idx = stt;

			while (i <= mid || j <= fin) {
				if (i == mid + 1) {
					sortedArr[idx] = arr[j];
					j++;
					idx++;
					cnt++;
					continue;
				}
				if (j == fin + 1) {
					sortedArr[idx] = arr[i];
					i++;
					idx++;
					cnt++;
					continue;
				}
				if (arr[i] >= arr[j]) {
					sortedArr[idx] = arr[j];
					j++;
					idx++;
					cnt++;
					continue;
				} else {
					sortedArr[idx] = arr[i];
					i++;
					idx++;
					cnt++;
				}
			}
			for (int k = 0; k < arr.length; k++) {
				arr[k] = sortedArr[k];
			}
		}
	}

}