public class Quick_sort {
   static void quick_sort2(int[] nums ,int l,int r) {
       _quick_sort2(nums,l,r);
       final_insert_sort(nums,l,r);
   }
   public static int threshold = 6;
   private static int median(int[] nums, int l, int r, int i) {
       if(nums[l]>nums[r]) swap(nums,l,r);
       if(nums[l]>nums[i]) swap(nums,l,i);
       if(nums[r]>nums[i]) swap(nums,r,i);
       return nums[r];
   }
   static void _quick_sort2(int[] nums,int l,int r){
       while(r-l>threshold) {
           int x = l,y = r,base = median(nums,l,r,(l+r)>>1);
           while(x<=y) {
               while(x <= y && nums[y] > base) {       //基准值右边的数大于基准值，不动它，让y–
                   y–;
               }
               while(x <= y && nums[x] < base) {       //基准值左边的数小于基准值，不动它，让x++
                   x++;
               }
               //此时x指的值大于基准值，y指的值小于基准值，让他们交换，完成一趟排序
               if(x<=y) {
                   swap(nums,x,y);
                   x++;
                   y–;
               }

           }
           _quick_sort2(nums,x,r);
           r = y;
       }

   }
   static void final_insert_sort(int[] nums,int l,int r) {
       int ind = l;
       for(int i = l+1;i<=r;i++) {
           if(nums[i]<nums[ind]) ind = i;
       }
       while(ind > l) {
           swap(nums,ind,ind-1);
           ind–;
       }
       for(int i = l+2;i<=r;i++) {
           int j = i;
           while(nums[j]<nums[j-1]) {
               swap(nums,j,j-1);
               j–;
           }
       }
   }
   static void swap(int[] nums,int x,int y) {
   int temp = nums[x];
   nums[x] = nums[y];
   nums[y] = temp;
   }
}