import java.util.*;

public class Solution {

    /**

     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

     * 将给定数组排序

     * @param arr int整型一维数组 待排序的数组

     * @return int整型一维数组

     */

    public int[] MySort (int[] arr) {

        quickSort(arr, 0, arr.length - 1);

        return arr;

    }

    public void quickSort(int[] arr, int low, int high) {

        if(low >= high) {

            return;

        }

        //枢纽元素的名字叫pivot

        int pivot = arr[low];

        int i = low, j = high;

        while(i < j) {

            //注意循环体，是先从右往左找

            while(i < j && arr[j] > pivot) {

                j--;

            }

            if(i < j) {

                arr[i++] = arr[j];

            }

            //再从左往右找

            while(i < j && arr[i] < pivot) {

                i++;

            }

            if(i < j) {

                arr[j--] = arr[i];

            }

        }

        //最后的位置才放入枢纽元素

        arr[i] = pivot;

        //注意递归的下标从哪里到哪里

        quickSort(arr, low, i - 1);

        quickSort(arr, i + 1, high);

    }

}