[백준] 1517번 : 버블 소트 - JAVA(자바)

https://www.acmicpc.net/problem/1517

아니 문제가 버블 정렬이라며
버블 정렬로 풀면 시간 초과가 나는 엄청난 문제

오답코드

package Doit알고리즘코딩테스트.정렬;// @ author ninaaano

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

/**
 * 문제 이름은 버블 소트인데 버블 소트로 풀면 시간초과가 나는 이상한 문제
 * 찾아보니 머지소트로 풀어야 한다고 한다
 */

public class P1517_버블소트 {
    static int swapped = 0;
    static int[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        bubble_sort(arr,arr.length);
        System.out.println(swapped);
    }

    private static int bubble_sort(int[] arr, int size) {
        for(int i = 1; i<size; i++){
            boolean isSwapped = false;
            for(int j=0; j<size-i; j++){
                if(arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                    isSwapped = true;
                    swapped++;
                }
            }
            // swap된 적 없다면 이미 정렬했단 의미기 때문에 반복문 종료
            if(!isSwapped){
                break;
            }
        }
        return swapped;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

중간에 boolean 변수를 추가해서 시간복잡도를 줄이려 했으나 대실패
merge sort가 도저히 이해가 안가서 블로그에서 찾아봤다.
코드 참고 블로그
봐도 무슨 소린지 모르겠다. 정리가 필요하다

정답코드

package Doit알고리즘코딩테스트.정렬;// @ author ninaaano

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

/**
 * 문제 이름은 버블 소트인데 버블 소트로 풀면 시간초과가 나는 이상한 문제
 * 찾아보니 머지소트로 풀어야 한다고 한다
 */

public class P1517_버블소트 {

    static long swapped;
    static long[] arr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new long[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        merge_sort(0,n-1);
        System.out.println(swapped);
    }

    private static long merge_sort(int start, int end) {
        if(start == end){
            return 0;
        }
        int mid = (start+end)/2;
        long[] sorted = new long[end - start + 1];
        swapped = merge_sort(start,mid) + merge_sort(mid+1,end);
        {
            int left = start; // 앞 부분 인덱스
            int right = mid+1; // 뒷 부분 인덱스
            int k = 0;

            while(left <= mid || right <= end){
                // right > end || 로 앞부분에 남아있을 경우 처리
                if(left <= mid && (right > end || arr[left] <= arr[right])){
                    sorted[k++] = arr[left++];
                }else{
                    swapped += mid-left+1; // 왼쪽의 남은 크기만큼 더한다
                    sorted[k++] = arr[right++];
                }
            }
        }
        for(int i = start; i<= end; i++){
            arr[i] = sorted[i-start];
        }
        return swapped;
    }
}