// Ordenar usando el método de mezcla natural
// Octubre de 2009 Con Clase, Salvador Pozo

#include <iostream>

using namespace std;

void Mostrar(int*, int);
int MezclaNatural(int*, int);

int main() {
    int vector[12] = { 34, 33, 23, 3, 54, 21, 1, 99, 12, 32, 51, 64 };

    cout << "Vector inicial:" << endl;
    Mostrar(vector, 12);
    while(MezclaNatural(vector, 12) > 1);
    cout << "Vector final:" << endl;
    Mostrar(vector, 12);
    return 0;
}

void Mostrar(int *v, int n) {
    int *f = &v[n]; // Puntero a posición siguiente al último elemento
    while(v < f) {
        cout << *v << " ";
        v++;
    }
    cout << endl;
}

int MezclaNatural(int *v, int n) {
    int *aux[2];
    int *iaux[2];
    int *iaux2[2];
    int *i, *f;
    int activa=0; // Activamos el primer vector auxiliar
    int tramo;
    bool tramonuevo;

    aux[0] = iaux[0] = new int[12];
    aux[1] = iaux[1] = new int[12];
    i = v;
    f = &v[n];
    // El primer elemento se copia siempre al primer vector:
    *iaux[activa]++ = *i++;
    // Separar vector en auxiliares:
    while(i < f) {
        if(*i < *(i-1)) activa++;
        if(activa >=2) activa -= 2;
        *iaux[activa]++ = *i++;
    }

    // Fundir vectores auxiliares:
    iaux2[0] = aux[0];
    iaux2[1] = aux[1];
    i = v;
    tramo = 0;
    tramonuevo = true;
    while(iaux2[0] < iaux[0] || iaux2[1] < iaux[1]) {
        if(tramonuevo) { // caso A
            // El primer elemento lo añadimos directamente:
            if(*iaux2[0] < *iaux2[1]) { *i++ = *iaux2[0]++; }
            else                      { *i++ = *iaux2[1]++; }
            tramo++;
            tramonuevo = false;
        } else           // caso B
        if(iaux2[0] == iaux[0]) {
            while(iaux2[1] < iaux[1]) {
                if(*iaux2[1] < i[-1]) tramo++;
                *i++ = *iaux2[1]++;
            }
        } else           // caso C
        if(iaux2[1] == iaux[1]) {
            while(iaux2[0] < iaux[0]) {
                if(*iaux2[0] < i[-1]) tramo++;
                *i++ = *iaux2[0]++;
            }
        } else           // caso D
        if(*iaux2[0] > i[-1] && *iaux2[1] > i[-1]) {
            if(*iaux2[0] < *iaux2[1]) { *i++ = *iaux2[0]++; }
            else                      { *i++ = *iaux2[1]++; }
        } else           // caso E
        if(*iaux2[0] > i[-1])
            while(iaux2[0] < iaux[0] && *iaux2[0] > i[-1]) {
                *i++ = *iaux2[0]++;
            }
        else             // caso F
        if(*iaux2[1] > i[-1])
            while(iaux2[1] < iaux[1] && *iaux2[1] > i[-1]) {
                *i++ = *iaux2[1]++;
            }
        else {           // caso G
            tramonuevo = true;
        }
    }
    delete[] aux[1];
    delete[] aux[0];
    return tramo;
}

Vector inicial:
34 33 23 3 54 21 1 99 12 32 51 64 
Vector final:
1 3 12 21 23 32 33 34 51 54 64 99