#include <stdio.h>
 
double FindMedian(int n, int *a);
 
int main(int argc, char* args[])
{
    double median;
    printf("\n\nMain ...\n\n");
    int x[3][3] = 
    {
       {1, 2, 3}, 
       {100, 10000, 20000}, 
       {1000, 30000, 40000}
    };

    int y[4][4] = 
    {
       {10, 20, 30, 40}, 
       {100, 10000, 20000, 30000}, 
       {1000, 30000, 35000, 40000},
       {10000, 35000, 40000, 45000}
    };

    median = FindMedian(3, (int *) x);
    printf("\nMedian : %lf\n", median);

    median = FindMedian(4, (int *) y);
    printf("\nMedian : %lf\n", median);

    return 0;
}

int GetMedianValue(int m, int mix, int six, int value, int *pfQuit)
{
    if (six == mix) 
    {
        printf("*");
        return value;
    }

    if (m % 2 == 0 && six == mix + 1)
    {
        *pfQuit = 1;
        printf("*");
        return value;
    }

    return 0;
}

double FindMedian(int n, int *a)
{
    int i, j, r, c;
    int six = 0; // Sorted Index Number
    int sixr, sixc;
    const int m = n * n;
    const int mix = (m + 1) >> 1; // Median Index Number
    long median = 0;
    int fQuit = 0;

    printf("\n\n\nNumber Of Elements = %d, Median Index = %d", m, mix);

    printf("\n\nMatrix : \n");

    for (i = 0; i < n; i++)
    {
        printf("\n");
        for (j = 0; j < n; j++)
        {
            printf("%d, \t\t", a[i*n + j]);
        }
    }

    printf("\n\nSequence : "); 
    for (i = 0; i < (n + 1)/ 2 && !fQuit; i++)
    {
        sixr = sixc = i; six++;
        median += GetMedianValue(m, mix, six, a[sixr*n + sixc], &fQuit);
        printf("%d, ", a[sixr*n + sixc]); 
        if (fQuit) break;
        for (r = i + 1, c = i + 1; r < n && c < n;)
        {
            if (a[i*n + c] < a[r*n + i])
            {
                six++;
                sixc = c++;
                median += GetMedianValue(m, mix, six, a[sixr*n + sixc], &fQuit);
                printf("%d, ", a[sixr*n + sixc]);
                if (fQuit) break;
            }
            else
            {
                six++;
                sixr = r++;
                median += GetMedianValue(m, mix, six, a[sixr*n + sixc], &fQuit);
                printf("%d, ", a[sixr*n + sixc]);
                if (fQuit) break;
            }
        }

        while (c < n && !fQuit)
        {
            six++;
            sixc = c++;
            median += GetMedianValue(m, mix, six, a[i*n + sixc], &fQuit);
            printf("%d, ", a[i*n + sixc]);
        }

        while(r < n && !fQuit)
        {
            six++;
            sixr = r++;
            median += GetMedianValue(m, mix, six, a[sixr*n + i], &fQuit);
            printf("%d, ", a[sixr*n + i]);
        }
    }

    return (m % 2 == 0) ? median / 2 : median;
}

Main ...




Number Of Elements = 9, Median Index = 5

Matrix : 

1, 		2, 		3, 		
100, 		10000, 		20000, 		
1000, 		30000, 		40000, 		

Sequence : 1, 2, 3, 100, *1000, 10000, 20000, 30000, 
Median : 1000.000000



Number Of Elements = 16, Median Index = 8

Matrix : 

10, 		20, 		30, 		40, 		
100, 		10000, 		20000, 		30000, 		
1000, 		30000, 		35000, 		40000, 		
10000, 		35000, 		40000, 		45000, 		

Sequence : 10, 20, 30, 40, 100, 1000, 10000, *10000, *20000, 
Median : 15000.000000