public class QuickOrder{

public void sort(int[] arr,int left,int right){

if(left >= right) return;

int[] scop = process(arr,left,right);

sort(arr,left,scop[0]-1);

sort(arr,scop[1]+1,right);

}

public int[] process(int[] arr,int left,int right){

if (left > right) { // L...R L>R

return new int[] { -1, -1 };

}

if (left == right) {

return new int[] { left, right };

}

int less = left -1;

int R = right-1;

int more = right;

int index = left;

swap(arr, left + (int) (Math.random() * (right - left + 1)),R);

while(index<more){

if(arr[index] == arr[R]){

index++;

}else if(arr[index] < arr[R]){

swap(arr,index++,++less);

}else if(arr[index] > arr[R]){

swap(arr,index,--more);

}

}

swap(arr,more,R);

return new int[]{less+1,more};

}

public void swap(int[] arr,int l,int r){

int t = arr[l];

arr[l] = arr[r];

arr[r] = t;

}

public static void main(String[] args){

QuickOrder t=new QuickOrder();

int[] arr={2,4,46,8};

//int[] result = t.process(arr,0,arr.length);

t.sort(arr,0,arr.length);

System.out.println();

for (int i=0; i<arr.length; i++) {

System.out.print(arr[i]+",");

}

System.out.println();

//System.out.println("["+result[0]+","+result[1]+"],ans = "+arr[result[0]]);

}

}