#include <iostream>
#include <time.h>
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <assert.h> 

using namespace std;


int Pivot2(vector<int> &v, int pivot) {

	vector<int> v_copy(v.size()); 
	//int pivot = v.size() / 2; 
	//1. Sort the array about the mid term  
	int count_less = 0; 
	int j = 0; 
	for (unsigned int i = 0; i <v.size() ; i++) {

		if (v[i]< v[pivot]) {
			v_copy[j]=v[i]; 
			j++; 
			count_less++; 
		}
	}

	v_copy[j]=v[pivot];
	j++; 
	
	for (unsigned int i = 0; i <v.size(); i++) {

		if (v[i]> v[pivot]) {
			v_copy[j] = v[i];
			j++; 
		}
	}

	//2.  if the number of less than  than tmp_med increase the middle postion 
	if ( count_less >  v.size() / 2) {
		Pivot2(v_copy,count_less-1);
	}
	else if (count_less ==  v.size() / 2) {
		cout <<"inner " <<  v[pivot] <<endl ; 
		return v[pivot]; //Why the recursion does not terminate with this return?
	}
	else {
	    if ( count_less < v.size() / 2) {
			Pivot2(v_copy, count_less + 1 );
		}
	}



}


int main() {
	// your code goes here
	int arr[] = { 8, 7, 3, 1, 9, 4, 6, 5, 2};
	int n = sizeof(arr) / sizeof(arr[0]); 
	//randomize(arr, n);
	vector<int> v( begin(arr), end(arr) );

	int med1 = Pivot2(v,v.size()/2);
	assert(5 == med1);
	cout << med1 <<endl ; 
	return 0;
}