#include <stdio.h>
#include <stdlib.h>

int linearMedian(int* a,int n, int k) {

	// pick random value 
	int r = a[n/2];
	int sl = 0;
	int sk = 0;
	int sr = 0;
	int *asl = (int*)malloc(n*sizeof(int));
	int *ask = (int*)malloc(n*sizeof(int));
	int *asr = (int*)malloc(n*sizeof(int));
	int i;
	
	for (i = 0; i < n; i++) {
		if (a[i] < r) {
			asl[sl] = a[i];
			sl++;
		}
		else if (a[i] == r) {
			ask[sk] = a[i];
			sk++;
		}
		else {
			asr[sr] = a[i];
			sr++;
		}
		// resort the numbers
	}	
	if ( (k+1) <= sl)
		return linearMedian(asl, sl, k);
	else if (sl < (k+1) && (sl + sk) >= (k+1))
		return ask[sk-1];
	else
		return linearMedian(asr, (sr), (k) - (sl+sk));

}

int main() {

	int *a = (int*)malloc(13*sizeof(int));
	a[0] = 0;
	a[1] = 1;
	a[2] = 2;
	a[3] = 3;
	a[4] = 4;
	a[5] = 5;
	a[6] = 6;
	a[7] = 7;
	a[8] = 8;
	a[9] = 9;
	a[10] = 10;
	a[11] = 11;
	a[12] = 12;
	int i;
	for (i = 0; i < 13; i++)	
		printf("Found median: %d\n", linearMedian(a, 13, i));
}