public int partition(int left, int right) throws InterruptedException{
		
		int i = left, j = right;
	    int pivot = values[(left + right) / 2];  //middle element as pivot
	    
	    while (i <= j) {
	    	sortStateLock.lock();
	    	try{
	    		pivotPos = (left+right)/2;
	    		while (values[i] < pivot){
	    			i++;			//increment elements to the left of the pivot until we find one that is larger than it
	    		}
	    		while (values[j] > pivot){
	    			j--;			//decrement elements to the right of the pivot until we find one that is smaller than it
	    		}
	    		if (i <= j) {
	    			swap(i, j);		//swap the two elements found
	    			markedPos1 = i;	
	    			markedPos2 = j;
	    			i++;
	    			j--;
	    		}
	    	}
	    	finally{
	    		sortStateLock.unlock();
	    	}
	    	pause(3);
	     }
	   return i;
	}