【AOJ ALDS1_5】B: Recursion/Divide and Conquer - Merge Sort

問題

Merge Sort | Aizu Online Judge

方針

• マージソートをします.
• INFを適当においたせいで無事に死んだ

コード

#include <iostream>
#include <cstdio>

using namespace std;

#define rep(i,n) REP(i,0,n)
#define REP(i,a,n) for(int i = a ; i < (int)n ; i++)
#define MAX_N 500002
#define INF 2000000000000

int n;
int data[MAX_N+1];
int comp;
int l[MAX_N/2+2];
int r[MAX_N/2+2];

void merge(int left, int right, int mid){
  rep(i, mid-left){
    l[i] = data[left + i];
  }

  rep(i, right-mid){
    r[i] = data[mid + i];
  }

  l[mid-left] = r[right-mid] = INF;
  
  int left_idx, right_idx;
  left_idx = right_idx = 0;
  REP(i,left,right){
    comp++;
    if(l[left_idx] <= r[right_idx]){
      data[i] = l[left_idx];
      left_idx++;
    }else{
      data[i] = r[right_idx];
      right_idx++;
    }
  }
}

void mergeSort(int left, int right){
  if(right - left > 1){
    int mid = (right + left)/2;
    mergeSort(left, mid);     // 左
    mergeSort(mid, right);    // 右
    merge(left, right, mid);  // マージ
  }
}

signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  rep(i, n){
    cin >> data[i];
  }
  comp = 0;
  
  mergeSort(0, n);

  rep(i, n-1){
    cout << data[i] << " ";
  }
  cout << data[n-1] << endl;
  cout << comp << endl;

}