백준 1517번. 버블 소트 (Java)

문제 링크 : https://www.acmicpc.net/problem/1517

문제 이름은 버블소트지만 버블소트로 풀면 틀리는 문제입니다.

N이 최대 500,000 이죠 O(n^2)을 돌리면 당연하게도 시간초과가 납니다.

우리가 구해야 하는건 swap하는 갯수입니다.

버블소트에서 swap이 발생하는 조건은 앞의 숫자가 뒤에 숫자보다 클 때입니다.

즉 a[i] > a[i+1] 일 때 swap이 발생합니다.

그러므로 머지 소트를 이용하여 정렬을 하되, 앞의 숫자가 뒤의 숫자보가 큰 경우에 카운트를 해주면 동일하게 swap 횟수를 구할 수 있습니다.

swapCount에 (mid+1-i) 를 더하는 이유는 왼쪽 배열에 남아있는 숫자만큼 계속 swap이 발생하기 때문입니다.