병합 정렬

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

1517번: 버블 소트

버블 소트는 낚시다.

N 범위가 500000 이고 제한시간 1초인데

O(N^2)을 쓴다? 절대로 못푼다

O(n log n)을 쓰자.

병합 정렬에서 두 그룹을 병합하는 과정에서

버블 정렬의 swap이 포함되어 있다

합치는 과정에서

뒤쪽 데이터가 더 작아 선택되는 경우

SWAP이 일어났다고 가정하며

현재 남아있는 앞쪽 데이터 개수만큼 결과값에 더함

 

result = result + index2 - k;

#include <iostream>
#include <vector>
using namespace std;
 
vector<int> arr;
vector<int> tmp;
 
long result;
 
void merge(int s, int e)
{
    if (e - s < 1)
        return;
 
    int m = s + (e - s) / 2;
    // 재귀 함수 형태
    merge(s, m);
    merge(m + 1, e);
 
    for (int i = s; i <= e; i++)
    {
        tmp[i] = arr[i];
    }
 
    int k = s;
    int index1 = s;
    int index2 = m + 1;
 
    while (index1 <= m && index2 <= e)
    {
        if (tmp[index1] > tmp[index2])
        {
            arr[k] = tmp[index2];
            //뒤쪽 데이터 값이 작아 선택되는 경우 결과 업데이트
            result = result + index2 - k;
            k++;
            index2++;
        }
        else
        {
            arr[k] = tmp[index1];
            k++;
            index1++;
        }
    }
 
    //한 쪽 그룹이 모두 선택된 후 남아있는 값 정리하기
    while (index1 <= m)
    {
        arr[k] = tmp[index1];
        k++;
        index1++;
    }
    while (index2 <= e)
    {
        arr[k] = tmp[index2];
        k++;
        index2++;
    }
}
 
int main()
{
    int n;
    cin >> n;
    arr = vector<int>(n + 1, 0);
    tmp = vector<int>(n + 1, 0);
    
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    result = 0;
    merge(1, n);
    cout << result << '\n';
}