합병 정렬

처음 입력으로 입력받을 숫자의 갯수 N을 입력받는다.
두 번째 입력으로 N만큼 숫자들을 한 줄로 입력받는다.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    // 입력 크기 받기
    // 받은 입력으로 배열 생성
    int N = Integer.parseInt(bufferedReader.readLine());
    int[] numbers = new int[N];
    // 숫자들 입력 받기
    StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
    // 입력 받은 수 가공해서 배열에 저장
    for (int i = 0; i < N; i++) {
      numbers[i] = Integer.parseInt(st.nextToken());
    }
    // merge sort 진행
    mergeSort(numbers, 0, numbers.length-1);

    for (int number : numbers) {
      bufferedWriter.write(number+" ");
    }

    bufferedWriter.flush();
    bufferedWriter.close();

  }

  /*
  * low 는 첫 인덱스
  * high 는 마지막 인덱스
  * */
  public static void mergeSort(int[] arr, int low, int high) {
    if (low >= high) return;

    int mid = (low + high) / 2;

    mergeSort(arr, low, mid);
    mergeSort(arr, mid+1, high);
    merge(arr, low, mid, high);
  }


  public static void merge(int[] arr, int low, int mid, int high) {
    // left 는 왼쪽 배열의 첫 인덱스
    // right 은 오른쪽 배열의 첫 인덱스
    // idx 는 mergedArr 의 첫 인덱스
    int left = low, right = mid+1, idx = 0;
    // 정렬된 배열을 할당하기 위해 정렬되는 크기만큼만 mergedArr 생성
    int[] mergedArr = new int[high-low+1];
    // left 와 right 가 둘 다 각각의 배열 크기 안에 속할 때
    while (left <= mid && right <= high) {
      if (arr[left] <= arr[right]) { // 값이 같을 때 교환해주지 않아야 in-place 로 가능
        mergedArr[idx++] = arr[left++];
      } else {
        mergedArr[idx++] = arr[right++];
      }
    }
    // 오른쪽 배열을 다 보고 왼쪽 배열만 남았을 때
    while (left <= mid) {
      mergedArr[idx++] = arr[left++];
    }
    // 왼쪽 배열을 다 보고 오른쪽 배열만 남았을 때
    while (right <= high) {
      mergedArr[idx++] = arr[right++];
    }
    // 정렬된 mergedArr 원소들을 arr 에 대입
    // 현재 정렬된 부분만 할당해야 하기 때문에 left ~ high 만큼만 반복
    for (int i = low; i < high+1; i++) {
      // mergedArr 는 매번 생성된 후 첫 인덱스부터 정렬된 값이 저장되어 있음.
      arr[i] = mergedArr[i-low];
    }
  }
}

전역 변수를 써서 풀기

package sort;

import java.io.*;
import java.util.StringTokenizer;

public class Main {
  public static int N;
  public static int[] numbers;
  public static int[] mergedArr;

  public static void main(String[] args) throws IOException {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    // 입력 크기 받기
    // 받은 입력으로 배열 생성
    N = Integer.parseInt(bufferedReader.readLine());
    numbers = new int[N];
    mergedArr = new int[N];
    // 숫자들 입력 받기
    StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
    // 입력 받은 수 가공해서 배열에 저장
    for (int i = 0; i < N; i++) {
      numbers[i] = Integer.parseInt(st.nextToken());
    }
    // merge sort 진행
    mergeSort(0, N-1);

    for (int number : numbers) {
      bufferedWriter.write(number+" ");
    }

    bufferedWriter.flush();
    bufferedWriter.close();

  }

  /*
  * low 는 첫 인덱스
  * high 는 마지막 인덱스
  * */
  public static void mergeSort(int low, int high) {
    if (low >= high) return;

    int mid = (low + high) / 2;

    mergeSort( low, mid);
    mergeSort( mid+1, high);
    merge( low, mid, high);
  }


  public static void merge(int low, int mid, int high) {
    // left 는 왼쪽 배열의 첫 인덱스
    // right 은 오른쪽 배열의 첫 인덱스
    // idx 는 mergedArr 의 인덱스
    int left = low, right = mid+1, idx = low;

    // left 와 right 가 둘 다 각각의 배열 크기 안에 속할 때
    while (left <= mid && right <= high) {
      if (numbers[left] <= numbers[right]) { // 값이 같을 때 교환해주지 않아야 in-place 로 가능
        mergedArr[idx++] = numbers[left++];
      } else {
        mergedArr[idx++] = numbers[right++];
      }
    }
    // 오른쪽 배열을 다 보고 왼쪽 배열만 남았을 때
    while (left <= mid) {
      mergedArr[idx++] = numbers[left++];
    }
    // 왼쪽 배열을 다 보고 오른쪽 배열만 남았을 때
    while (right <= high) {
      mergedArr[idx++] = numbers[right++];
    }
    // 정렬된 mergedArr 원소들을 numbers 에 대입
    for (int i = low; i <= high; i++) {
      numbers[i] = mergedArr[i];
    }
  }
}