class QuickSort{

    public void sort(int[] A){
        sort(A,0,A.length-1);
    }

    private void sort(int[] A, int low, int high){
        if(low<high) {
            int pivot_pos = partition(A,low,high);
            sort(A,low,pivot_pos-1);
            sort(A,pivot_pos+1,high);
        }
    }

    private int partition(int[] A, int low, int high){
        int pivot = A[low];
        while(low<high){
            //1.1：将high递减，直到找到小于pivot的元素为止
            while(low<high&&A[high]>=pivot){--high;}
            //1.2 将low所指向的为止用这个元素填充(原有元素已经保存在pivot中，不会丢失）
            A[low] = A[high];
            //2.x 同理，low递增，直到找到大于pivot的元素为止
            while(low<high&&A[low]<=pivot){++low;}
            //覆盖原先A[high]所在位置
            A[high] = A[low];
        }
        //此时low=high
        A[low] = pivot;
        return low;
    }
}

class ShellSort{
    public void sort(int[] A){
        //步长、临时变量、组间指针、组内指针
        int step_length,tmp,inter_group_ptr,inner_group_ptr;
        int len = A.length;
        //步长按照数组长度/2向下取整，逐级递减
        for(step_length = len/2;step_length>=1;step_length/=2){
            //在分组之间来回切换，组间指针从第一个分组的第二个数开始处理
            for(inter_group_ptr=step_length; inter_group_ptr < len; inter_group_ptr++){
                //每一个分组的前一个数都应该小于后一个，否则进行调整
                if(A[inter_group_ptr-step_length]>A[inter_group_ptr]){
                    //将组间指针指向的数保存在临时变量中
                    tmp = A[inter_group_ptr];
                    //组内指针的初始位置是组间指针指向的数所属组的前一个数
                    inner_group_ptr = inter_group_ptr - step_length;
                    //只要下标不越界，且临时变量中的数没有放到正确的位置
                    while(inner_group_ptr>=0&&tmp<A[inner_group_ptr]){
                        //后移组内指针所指对象（A[inter_group_ptr]已经被覆盖）
                        A[inner_group_ptr+step_length]=A[inner_group_ptr];
                        //前移组内指针
                        inner_group_ptr-=step_length;
                    }
                    //将临时变量放到它在组内合理的位置
                    A[inner_group_ptr+step_length] = tmp;
                }
            }
        }
    }
}

class HeapSort{

    public void sort(int[] A){
        BuildMaxHeap(A);
        int heapTop = 0;
        //注意当heapBottom = heapTop+1时，意味着只剩下两个元素需要调整了，此时再进行调整有会把两个元素中较大的重新排到前面，即前两个元素会乱序
        //当heapBottom=headTop时，循环退出
        for(int heapBottom = A.length-1; heapBottom>heapTop ;--heapBottom){
            //交换堆顶元素和堆底元素
            int tmp = A[heapBottom];
            A[heapBottom] = A[heapTop];
            A[heapTop] = tmp;
            //调整堆（此时最后一个元素已经排好序了，不参与调整
            HeadAdjust(A,heapTop,heapBottom-1);
        }
        //恢复前两个元素的次序
        A[heapTop] = A[heapTop]^A[heapTop+1];
        A[heapTop+1]=A[heapTop]^A[heapTop+1];
        A[heapTop] = A[heapTop]^A[heapTop+1];
    }

    public void BuildMaxHeap(int[] A){
        int len = A.length;
        //在完全二叉树中，下标不大于length/2-1的节点都有子树(下标从0开始)
        for(int curRoot=len/2-1;curRoot>=0;--curRoot){
            HeadAdjust(A,curRoot,len);
        }
    }

    private void HeadAdjust(int[] A,int root,int len){
        int tmp = A[root];//临时变量，用于存储当前根节点的信息
        //先进入到当前节点的左子树
        int curNode = 2*root + 1;
        //当前节点的下标没有越界，说明还在堆的范围内
        while (curNode<len){
            //curNode<len-1用于检测最后一个有子树的节点的右子树的存在性，如果它没有右子树，那么左子树的下标就是len-1,否则为len-2
            //比较左右子树
            if(curNode<len-1&&A[curNode]<A[curNode+1]){
                //挑出较大的一个子节点
                ++curNode;
            }
            //根节点大于两个直接相连的子树，不用继续调整
            if(tmp>=A[curNode]) break;
            else{
                //用当前节点的值覆盖根节点
                A[root] = A[curNode];
                //以当前节点为根，下次循环继续调整
                root = curNode;
            }
            //进入当前节点的左子树
            curNode = 2*curNode + 1;
        }
        //将临时变量放到它应该在的地方(root的值在循环中可能已被修改)
        A[root] = tmp;
    }
}

class MergeSort{
    public void sort(int[] A){
        sort(A,0,A.length-1);
    }
    private void merge(int[] A,int low,int mid,int high){
        //route_x：归并线路x，global_ptr：全局指针
        int route_1,route_2,global_ptr;
        int[] tmp_arr = new int[A.length];
        for(global_ptr = low; global_ptr <= high; global_ptr++){
            tmp_arr[global_ptr] = A[global_ptr];
        }
        //现在进行二路归并，第一路从low开始，直到mid为止，第二路从mid+1开始，直到high为止，从而实现在low到high范围内的归并
        for(route_1=low,route_2=mid+1,global_ptr=route_1;route_1<=mid&&route_2<=high;global_ptr++){
            if(tmp_arr[route_1]<=tmp_arr[route_2]) A[global_ptr] = tmp_arr[route_1++];
            else A[global_ptr] = tmp_arr[route_2++];
        }
        //这两个循环并不会被执行太多次，因为mid=(low+high)/2
        while(route_1<=mid) A[global_ptr++]=tmp_arr[route_1++];
        while(route_2<=high) A[global_ptr++]=tmp_arr[route_2++];
    }
    private void sort(int[] A,int low,int high){
        if(low<high){
            int mid = (low+high)/2;
            sort(A,low,mid);
            sort(A,mid+1,high);