Mergesort

mergesort.cpp

using namespace std;
#include <algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>

#define foreach(x, v) for (typeof (v).begin() x=(v).begin(); x !=(v).end(); ++x)
#define For(i, a, b) for (int i=(a); i<(b); ++i)
#define D(x) cout << #x " is " << x << endl

const int MAXN = 100000;
vector <int> a;
vector <int> test;

vector <int> merge (int i, int j, int m){
    // printf("Calling merge(%d, %d)\n", i, j);
    vector <int> ans;
    int i1 = i;
    int j1 = m + 1;
    int n = j - i + 1;
    while (i1 <= m and j1 <= j){
        if (a[i1] < a[j1]){
            ans.push_back(a[i1]);
            i1++;
        }else{
            ans.push_back(a[j1]);
            j1++;
        }
    }
    for (; i1 <= m; i1++) ans.push_back(a[i1]);
    for (; j1 <= j; j1++) ans.push_back(a[j1]);
    
    return ans;
}


void srt(int i, int j){
    // printf("Calling sort(%d, %d)\n", i, j);
    if (i == j) return;
    int m = (j + i) / 2;
    srt(i, m);
    srt(m + 1, j);
    vector <int> b = merge(i, j, m);
    for (int k = 0; k < b.size(); k++){
        a[k + i] = b[k];
    }
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        int x;
        cin >> x;
        a.push_back(x);
        test.push_back(x);
        
    }    
    srt(0, n - 1);
    sort(test.begin(), test.end());
    for (int i = 0; i < n; i++) assert(a[i] == test[i]);

    printf("The sorted array:\n");
    for (int k = 0; k < a.size(); k++){
        printf("%d ", a[k]);
    }
    printf("\n");
    
    return 0;
}