Test with 8 integers
        OK
Test with 16 integers
        OK
Test with 32 integers
        OK
Test with 64 integers
        OK
Test with 128 integers
        OK
Test with 256 integers
        OK
Test with 512 integers
        OK

void median(int t[], int n){
    int m = ((n - 1) / 2);
    if (t[0] > t[n - 1]) {   /* t[0] > t[n - 1] */
        if (t[m] >  t[0]);  /*  t[m] > t[0] > t[n - 1] */

        else if (t[n - 1] > t[m]) /*  t[0] > t[n - 1] > t[m] */
            swap(t[0], t[n-1]);

        else /*  t[0] >= t[m] >= t[n - 1] */
            swap(t[0], t[m]);

    } else { /* t[0] <= t[n - 1] */
        if (t[m] < t[0]) ; /*  t[m] < t[0] <= t[n - 1] */

        else if (t[n - 1] < t[m]) /*  t[0] <= t[n - 1] < t[m] */
            swap(t[0], t[n-1]);

        else    /* t[0] <= t[m] <= t[n + 1] */
            swap(t[0], t[m]);
    }

}

int partition( int t[], int n) {
    int l = 0, r = n, tmp;

    median(t, r);

    while(1) {
        do
            ++l;
        while(l < n &&  t[l] < t[0]); // l <= n-1
        do
            --r;
        while(t[r] > t[0]); // r >= 0
        if( l >= r )
             break;
        tmp = t[l];
        t[l] = t[r];
        t[r] = tmp;
    }
    tmp = t[0];
    t[0] = t[r];
    t[r] = tmp;

    return r;
}

void version2(int t[], int size) {

    int m, l = 0, r = size ;
    while((r - l) > 1) {

        m = partition( t + l, r);
        if( (m - l) < (r - m)){
            version2(t + l, m);
            l = m + 1;
        }
        else{
            version2(t + m + 1, r);
            r = m;
        }
    }

}

Test with 8 integers