정렬 - Merge Sort

퀵소트는 정렬하고 분할하여 반복하지만, 얘는 분할하고 정렬하며 다시 올라옴
퀵소트는 내려가면서 정렬, 얘는 올라오면서 정렬

반 가르고 왼쪽범위에 대해서 mergeSort후, 오른쪽범위에 대해서 mergeSort _범위의 left가 right보다 큰경우 return(boundary condition)
각 배열의 첫번째 index부터 비교해가며 큰쪽을 새배열에 넣음
각 배열중 한쪽을 다 넣었으면 다른 한쪽은 뒤에 그냥 갖다붙이기 _어차피 더 큰수들이 정렬되어 있으므로

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

public class Main{
        public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        mergeSort(arr, 0, arr.length - 1);

            StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i] + "\n");
        }
            System.out.println(sb.toString());
    }

    static void mergeSort(int[] arr, int left, int right) {

        if (left >= right) {
            return;
        }
        //왼쪽, 오른쪽으로 분할
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 왼쪽 배열과 오른쪽 배열로 나누기(left배열, right배열 생성 후 복붙)
        int leftSize = mid - left + 1;
        int rightSize = right - mid;

        int[] leftArr = new int[leftSize];
        int[] rightArr = new int[rightSize];

        for (int i = 0; i < leftSize; i++) {
            leftArr[i] = arr[left+i];
        }
        for (int i = 0; i < rightSize; i++) {
            rightArr[i] = arr[mid + 1 + i];
        }

        // 비교하면서 원본 배열에 넣기
        // arr의 left인덱스부터 채우기
        // left와 right 각각 pointer
        // left의 pointer와 right의 pointer를 비교해서 작은쪽을 넣고 ++
        // 한쪽을 다 넣을때까지
        // 다 넣으면 남은쪽 나머지 마저 넣기
        int LPointer = 0;
        int RPointer = 0;
        int insertPointer = left;
        while(true){
            if (LPointer >= leftSize || RPointer >= rightSize) {
                break;
            }
            if (leftArr[LPointer] < rightArr[RPointer]) {
                arr[insertPointer] = leftArr[LPointer];
                insertPointer++;
                LPointer++;
            }else{
                arr[insertPointer] = rightArr[RPointer];
                insertPointer++;
                RPointer++;
            }
        }
        
        while(LPointer < leftSize){
            arr[insertPointer] = leftArr[LPointer];
            insertPointer++;
            LPointer++;
        }
        
        while (RPointer < rightSize) {
            arr[insertPointer] = rightArr[RPointer];
            insertPointer++;
            RPointer++;
        }
    }
}

* System.out.println()사용시 시간초과 -> StringBuilder사용
* QuickSort는 pivot을 기준으로 왼쪽 오른쪽을 정렬하므로 pivot을 제외한 pivot-1, pivot+1의 범위에 대해 분할 하지만, MergeSort는 그런거 없이 mid, mid+1 의 범위로 모두 분할해줘야 한다는점 참고