Mergesort

Mergesort is one of the best-known examples of the unility of the divide-and-conquer paradigm for efficent algorithm design. It is as good as Quicksort.

#include<cstdio>
#include<iostream>
using namespace std;

void Merge int a[], int first, int mid, int last ) {
    int b[1000], e;
    int i = first;
    int j = mid + 1;
    int len = last - first + 1;
    for e = 0; e < len; e++ ) {
        if i == mid + 1 ) b[e] = a[j++];
        else if j == last +1 ) b[e] = a[i++];
        else if a[i] < a[j] ) b[e] = a[i++];
        else b[e] = a[j++];
    }
    for int k = 0; k < len; k++ ) {
        a[first + k] = b[k];
    }
}

void Mergesort int a[], int first, int last ) {
    int mid =  first + last ) / 2;
    if first < last ) {
        Mergesort a, first, mid );
        Mergesort a, mid + 1, last );
        Merge a, first, mid, last);
    }
}

int main)
{
    int n;
    while cin >> n ) {
        int a[1000];
        for int i = 0; i < n; i++ ) {
            cin >> a[i];
        }
        Mergesort a, 0, n - 1 );
        for int i = 0; i < n; i++) {
            cout << a[i] << ' ';
        }
        cout << endl;
    }
    return 0;
}