排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        sort(arr);
        return arr;
    }
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        sort(arr, 0, arr.length - 1);
        return arr;
    }
    
    public void sort(int[] a, int low, int high) {
        // 递归终止条件
        if(low >= high) {
            return;
        }
        int i = low;
        int j = high;
        // 基准位
        int temp = a[low];
        while(i < j) {
            // 找出从右到左第一个小于基准位的数下标
            while(i < j && temp <= a[j]) {
                j--;
            }
            // 找出从左到右第一个大于基准位的数下标
            while(i < j && temp >= a[i]) {
                i++;
            }
            if(i < j) {
                swap(a, i, j);
            }
        }
        // 此时 i==j
        swap(a, low, i);
        sort(a, low, i-1);
        sort(a, i+1, high);
    }
    
    public void swap(int[] a, int i, int j) {
        int c = a[i];
        a[i] = a[j];
        a[j] = c;
    }
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        mySort1(arr);
        return arr;
    }
    // 1、快速排序（通过）
    // 时间复杂度O(logn)。空间复杂度是O(n)。
    // 主要是要找出标杆值（中间值），默认最后一个值为标杆值，然后比它小的放左边，比他大的放右边，然后交换最后一位。就得到标杆值在中间的下标。
// 树，从上往下排序
    // 不稳定算法
    void mySort1(vector<int>& arr) {
        quicksort(arr, 0, arr.size()-1);
    }  
    void quicksort(vector<int> &arr, int left, int right) {
        if (left > right) return;

        int pivotIndex = partition(arr, left, right); // 标杆值所在的位置
        quicksort(arr, left, pivotIndex-1); // 左半边
        quicksort(arr, pivotIndex+1, right); // 右半边
    }
    // 这里只需要把数据归类就行，不需要比较大小；每次比标杆值小的放左边，比标杆值大的放右边。
    int partition(vector<int> &arr, int left, int right) {
        // 最后一个值当做标杆（自己随意定）
        int mark = arr[right];
        // 记录小于标杆值的个数
        int counter = left;      
        for (int i = left; i < right; i++) {
            if (arr[i] < mark) { // 当前值和标杆值比较，决定是放在左边还是右边
               swap(arr[i], arr[counter++]);
           }
        }
        swap(arr[counter], arr[right]);   // 最后把标杆值移到中间位置，然后返回下标。
        return counter;
    }


    // 2、归并排序（通过）
    // 时间复杂度O(logn)。空间复杂度是O(n)。
    // 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
    // 树，从下往上排序
    // 是稳定的算法
    void mySort2(vector<int>& arr) {
        mergeSort(arr, 0, arr.size()-1);
    }  

    void mergeSort(vector<int> &arr, int left, int right) {
        if (left >= right) return;

        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid); // 递归 左半边
        mergeSort(arr, mid+1, right); // 递归 右半边

        merge(arr, left, mid, right); // 合并两个有序的数组（参考合并两个有序的链表）
    }

    // 合并两个有序数组
    void merge(vector<int> &arr, int left, int mid, int right) {
        vector<int> tmp(right-left+1); // 开辟新的数组
        int i = left, j = mid+1, k = 0; // i左边数组的起始位置，j右边数组的起始位置，k已经放入新数组的个数

        while (i <= mid && j <= right) {  // 比较左右数组，数值小的放入新数组中
            tmp[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) tmp[k++] = arr[i++];  // 如果左半边数组没有排序完，加入新数组
        while (j <= right) tmp[k++] = arr[j++]; // 如果右半边数组没有排序完，加入新数组

        for (i = left, k = 0; i <= right;) arr[i++] = tmp[k++]; // 新数组数据放回到原来的数组中
    }
    // 3、堆排序（通过）
    // 时间复杂度O(logn)。空间复杂度是O(n)。
    // 不稳定算法
    void heapSort(vector<int> &arr) {
        priority_queue<int,vector<int>,greater<int>> q; //小顶堆

        for (int i = 0; i < arr.size(); i++) {
            q.push(arr[i]);
        }
        for (int i = 0; i < arr.size(); i++) {
            arr[i] = q.top();
            q.pop();
        }
    }

    // 4、冒泡排序（超时）
    // 时间复杂度O(n2)，空间复杂度O(1)
    // 从后往前排
    // 两两比较交换，最大的放在后面，稳定排序
    void bubbleSort(vector<int>& arr) {

        for (int i = 0; i < arr.size(); i++) {
            for (int j = 0; j < arr.size()-i-1; j++) {
                if (arr[j]>arr[j+1]) {
                    swap(arr[j], arr[j+1]);
                }
            }
        }
    }

    // 5、选择排序（超时）
    // 时间复杂度O(n2)，空间复杂度O(1)
    // 从前往后排
    // 遍历数组，找出最小值，最小的放在前面，不稳定排序
    void selectionSort(vector<int>& arr) {
        int minIndex = 0;
        for (int i = 0; i < arr.size(); i++) {
            minIndex = i;
            for (int j = i+1; j < arr.size(); j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            swap(arr[i], arr[minIndex]);
        }
    }

    // 6、插入排序（超时）
    // 时间复杂度O(n2)，空间复杂度O(1)
    // 从前往后排
    // 遍历数组，找出一个值，往排好的数组里面插入合适的位置。稳定排序
    void insetionSort(vector<int>& arr) {
        int preIndex = 0;
        int currentVal = 0;

        for (int i = 1; i < arr.size(); i++) {
            preIndex = i - 1;
            currentVal = arr[i];

            while (preIndex >= 0 && arr[preIndex] > currentVal) {
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = currentVal;
        }
    }


};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 将给定数组排序
 * @param arr int整型一维数组 待排序的数组
 * @param arrLen int arr数组长度
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
#include<stdio.h>
void Swap(int* p1, int* p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}

// 冒泡排序会超时
void BuubleSort(int* arr, int arrlen)
{
    for (int i = 0; i < arrlen; i++)
    {
        for (int j = 1; j < arrlen; j++)
        {
            if (arr[j - 1] > arr[j])
            {
                Swap(&arr[j - 1], &arr[j]);
            }
        }
    }
}

// 选择排序超时
void SelectSort(int* arr, int arrlen)
{
    int begin = 0;
    int end = arrlen - 1;

    while (begin <= end)
    {
        int maxi = begin;
        int mini = begin;
        for (int i = begin; i <= end; i++)
        {
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }

            if (arr[i] < arr[mini])
            {
                mini = i;
            }
        }

        Swap(&arr[begin], &arr[mini]);
        if (maxi == begin)
        {
            maxi = mini;
        }
        Swap(&arr[maxi], &arr[end]);

        end--;
        begin++;
    }
}
//插入排序 (可以通过)
void InsertSort(int* arr, int arrlen)
{
    for (int i = 0; i < arrlen - 1; i++)
    {
        int end = i;
        int key = arr[end + 1];
        /*while (end >= 0)
        {
            while (arr[end] > key)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            arr[end + 1] = key;
            break;
        }
        */
        while (end >= 0)
        {
            if (arr[end] > key)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            else
            {
                break;
            }
        }
        arr[end + 1] = key;
    }
}

//希尔排序通过
void ShellSort(int* arr, int arrLen)
{
    int gap = arrLen;
    while (gap > 1)
    {
        gap = gap / 2;

        for (int i = 0; i < arrLen - gap; i++)
        {
            int end = i;
            int key = arr[end + gap];

            while (end >= 0)
            {
                if (arr[end] > key)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = key;
        }

    }
}

//挖坑法的快速排序
int PartSort(int* arr, int left, int right)
{
    int pvoit = left;
    int key = arr[pvoit];
    while (left < right)
    {
        while (left < right && arr[right] >= key)
        {
            right--;
        }
        arr[pvoit] = arr[right];
        pvoit = right;

        while (left < right && arr[left] <= key)
        {
            left++;
        }
        arr[pvoit] = arr[left];
        pvoit = left;
    }
    arr[pvoit] = key;
    return  pvoit;
}


void QuickSort(int* arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int pvoit = PartSort(arr, left, right);
    QuickSort(arr, left, pvoit - 1);
    QuickSort(arr, pvoit + 1, right);


}

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{
    if (left >= right)
    {
        return;
    }
    int mid = (left + right) >> 1;
    _MergeSort(arr, left, mid, tmp);
    _MergeSort(arr, mid + 1, right, tmp);

    int begin1 = left;
    int end1 = mid;
    int begin2 = mid + 1;
    int end2 = right;
    int index = left;
    while (begin1 <= end1 && begin2 <= end2)
    {
        if (arr[begin1] < arr[begin2])
        {
            tmp[index++] = arr[begin1++];
        }
        else
        {
            tmp[index++] = arr[begin2++];
        }
    }

    while (begin1 <= end1)
    {
        tmp[index++] = arr[begin1++];
    }
    while (begin2 <= end2)
    {
        tmp[index++] = arr[begin2++];
    }

    for (int i = left; i <= right; i++)
    {
        arr[i] = tmp[i];
    }

}
void MergeSort(int* arr, int left, int right)
{
    int* tmp = (int*)malloc(sizeof(int) * (right - left + 1));
    _MergeSort(arr, left, right, tmp);
    free(tmp);
    tmp = NULL;

}

void AdjustDwon(int* arr, int arrLen, int root)
{
    int parent = root;
    int child = parent * 2 + 1;//默认是左孩子

    while (child < arrLen)
    {
        if (child + 1 < arrLen && arr[child + 1] > arr[child])
        {
            child += 1;
        }

        if (arr[child] > arr[parent])
        {
            Swap(&arr[child], &arr[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
void HeapSort(int* arr, int arrLen)
{
    //建堆
    for (int i = (arrLen - 1 - 1) / 2; i >= 0; i--)
    {
        AdjustDwon(arr, arrLen, i);
    }

    int end = arrLen - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        AdjustDwon(arr, end, 0);
        end--;
    }
}
int* MySort(int* arr, int arrLen, int* returnSize)
{
    // write code here
    //BuubleSort(arr, arrLen);
    //SelectSort(arr, arrLen);
    //InsertSort(arr, arrLen);
    //ShellSort(arr, arrLen);
    //MergeSort(arr, 0, arrLen - 1);
    //HeapSort(arr, arrLen);
    QuickSort(arr, 0,arrLen - 1);
    *returnSize = arrLen;
    return arr;
}

//此代码适用于像我这样的萌新小白们，直接使用数组自带的sort方法排序，代码简洁可读性高，
//缺点就是运行时间长，在大佬眼里的破代码哈哈哈。
import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        if(arr==null){
            return null;
        }
        if(arr!=null){
            Arrays.sort(arr);
        }
        return arr;
    }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        
        // write code here
        //==========================
        //冒泡排序
//         int temp = 0;
//         for(int i=0;i<arr.length-1;i++){
//             for(int j=0;j<arr.length-i-1;j++){
//                 if(arr[j]>arr[j+1]){
//                     temp = arr[j];
//                     arr[j] = arr[j+1];
//                     arr[j+1] = temp;
//                 }
//             }
//         }
//         return arr;
        //==========================
        //冒泡改进版
//         int len = arr.length;
//         while(len>0){
//             for(int i=0;i<len-1;i++){
//                 int next = i+1;
//                 if(arr[i]>arr[next]){
//                     int temp = arr[i];
//                     arr[i] = arr[next];
//                     arr[next] = temp;
//                 }
//             }
//             len--;
//         }
//         return arr;
        //==========================
        //快速排序
//         quicksort(arr,0,arr.length-1);
//         return arr;
        //==========================
        //选择排序
//             for(int i=0;i<arr.length;i++){
//                 int minIndex = i;
//                 for(int j=i;j<arr.length;j++){
//                     if(arr[j]<arr[minIndex]){
//                         minIndex = j;
//                     }
//                 }
//                 int temp = arr[i];
//                 arr[i] = arr[minIndex];
//                 arr[minIndex] = temp;
//             }
//         return arr;
        //==========================
        //插入排序
//         int current;
//         for(int i=0;i<arr.length-1;i++){
//             //拿出第一个未排序数（待插入数）
//             current = arr[i+1];
//             //设置最后一个已排序位置
//             int preIndex = i;
//             //依次对比拿出来的数，如果此数比待插入大，
//             //就往后移动一位（第一次循环会覆盖current的位置）
//             while(preIndex>=0 && current<arr[preIndex]){
//                 //往右移动
//                 arr[preIndex+1] = arr[preIndex];
//                 //待插入数位置往左移动
//                 preIndex--;
//             }
//             //当遇到比待插入数小的数时候停止循环，此时preIndex已经向左移动了，
//             //+1移动回来到空位，插入
//             arr[preIndex+1] = current;
//         }
//         return arr;
        //==========================
        //希尔排序
//         for(int gap=arr.length/2; gap>=1 ;gap/=2){
//             for(int i=0;i<arr.length-gap;i+=gap){
//                 int index = i;
//                 int current = arr[i+gap];
//                 while(index >= 0 && current < arr[index]){
//                     arr[index+gap] = arr[index];
//                     index -= gap;
//                 }
//                 arr[index + gap] = current;
//             }
//         }
        //归并排序调用
//         return sort(arr);
        //堆排序调用
//         sort(arr);
        //计数排序调用
//         return countingSort(arr,getMaxValue(arr));
        
        return bucketSort(arr,100);
//             return arr;
     }
    
    
//------------------------------------------------------------------------------------------
    
    
    
    //==========================
    
    //归并排序
    //归并递归
//     public static int[] sort(int[] arr){
//         if(arr.length<2){
//             return arr;
//         }
//         int middle = (int)Math.floor(arr.length/2);//例2.5-->2
        
//         int[] left = Arrays.copyOfRange(arr,0,middle);
//         int[] right = Arrays.copyOfRange(arr,middle,arr.length);
        
//         return merge(sort(left),sort(right));
//     }
    
//     //合并
//     public static int[] merge(int[] left,int[] right){
//         int[] result = new int[left.length+right.length];
//             int i = 0;
//             //当两组都有数时
//             while(left.length > 0 && right.length > 0){
//                 //如果左边的小，把左边的头数放入结果数组，删除left第一个数，使下一个数变成头数
//                 if(left[0] <= right[0]){
//                     result[i++] = left[0];
//                     left = Arrays.copyOfRange(left,1,left.length);
//                 }else{
//                     result[i++] = right[0];
//                     right = Arrays.copyOfRange(right,1,right.length);
//                 }
//             }
//             //当仅剩左数组有数时
//             while(left.length > 0){
//                 result[i++] = left[0];
//                 left = Arrays.copyOfRange(left,1,left.length);
//             }
//             //同理
//             while(right.length > 0){
//                 result[i++] = right[0];
//                 right = Arrays.copyOfRange(right,1,right.length);
//             }      

//             return result;
//     }
    //==========================
    
    //计数排序（测试数据的数很大，会出现数组越界）
    
//     public int[] countingSort(int[] arr,int maxvalue){
//         int bucketLen = maxvalue + 1;
//         int[] bucket = new int[bucketLen];
        
//         //计数数组
//         for(int value:arr){
//             bucket[value]++;
//         }
        
//         //结果数组待添加的位置
//         int sortedIndex = 0;
//         for(int j=0;j<bucketLen;j++){
//             while(bucket[j]>0){
//                 arr[sortedIndex++] = j;
//                 bucket[j]--;
                
//             }
//         }
//         return arr;
//     }
    
//     public int getMaxValue(int[] arr){
//         int maxvalue = arr[0];
//         for(int value:arr){
//             if(value > maxvalue){
//                 maxvalue = value;
//             }
//         }
//         return maxvalue;
//     }
    //==========================
    //桶排序（对于大数效率还是很低）
//     private int[] bucketSort(int[] arr,int bucketSize){
//         int minvalue = arr[0];
//         int maxvalue = arr[0];
//         for(int value:arr){
//             if (value < minvalue) {
//                 minvalue = value;
//             } else if (value > maxvalue) {
//                 maxvalue = value;
//             }
//         }
//         int bucketCount = (int) Math.floor((maxvalue-minvalue)/bucketSize)+1;
//         int[][] buckets = new int[bucketCount][0];
//         //分配到桶
//         for(int i=0;i<arr.length;i++){
//             int index = (int)Math.floor((arr[i]-minvalue)/bucketSize);
//             buckets[index] = arrAppend(buckets[index],arr[i]);
//         }
//         //装入结果数组
//         int arrIndex = 0;
//         for(int[] bucket:buckets){
//             if(bucket.length<=0){
//                 continue;
//             }
//             //排序单个桶的数据
//             //用希尔排序（原用插入排序）
//             for(int gap=bucket.length/2; gap>=1 ;gap/=2){
//             for(int i=0;i<bucket.length-gap;i+=gap){
//                 int index = i;
//                 int current = bucket[i+gap];
//                 while(index >= 0 && current < bucket[index]){
//                     bucket[index+gap] = bucket[index];
//                     index -= gap;
//                 }
//                 bucket[index + gap] = current;
//             }
//         }
            
            
//             for(int value:bucket){
//                 arr[arrIndex++] = value;
//             }
//         }
//         return arr;
//     }
    
//     //数组扩容插入
//     private int[] arrAppend(int[] arr, int value){
//         arr = Arrays.copyOf(arr,arr.length + 1);
//         arr[arr.length-1] = value;
//         return arr;
//     }
    //==========================
    //堆排序
    
//     public int[] sort(int[] arr){
//         int len = arr.length;
//         buildMaxheap(arr,len);
        
//         for(int i = len -1;i>0;i--){
//             swap(arr,0,i);
//             len--;
//             heapify(arr,0,len);
//         }
//         return arr;
//     }
    
//     //将整个数组整理成大根数
//     public void buildMaxheap(int[] arr,int len){
//         for(int i = (int)Math.floor(len/2);i>=0;i--){
//             heapify(arr,i,len);
//         }
//     }
    
//     //下滤
//     public void heapify(int[] arr,int i,int len){
//         int left = 2*i+1;
//         int right = 2*i+2;
//         int largest = i;
        
//         if(left<len && arr[left]>arr[largest]){
//             largest = left;
//         }
//         if(right<len && arr[right]>arr[largest]){
//             largest = right;
//         }
        
//         if(largest != i){
//             swap(arr,i,largest);
//             heapify(arr,largest,len);
//         }
//     }
    
//     public void swap(int[] arr, int i, int j) {
//         int temp = arr[i];
//         arr[i] = arr[j];
//         arr[j] = temp;
//     }
    
    
    
    
    //==========================
    //快速排序递归方法
//     public static void quicksort(int[] target,int left,int right){
//                 if(left>=right){
//                     return;
//                 }
//                 int pivot = target[left];
//                 int l = left;
//                 int r = right;
//                 while(l < r){
//                     while(target[r] >= pivot && l<r){
//                         r --;
//                     }
//                     target[l] = target[r];
//                     while(target[l]<=pivot && l<r){
//                         l ++;
//                     }
//                     target[r] = target[l];
//                 }
//                 target[l] = pivot;
//                 quicksort(target,left,l-1);
//                 quicksort(target,r+1,right); 
//             }
}

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        // 快速排序，时间复杂度O(N*logN)，空间复杂度O(logN)，不稳定
        quickSort(arr, 0, arr.length - 1);
        // 归并排序，时间复杂度O(N*logN)，空间复杂度O(N)，稳定
        // mergeSort(arr);
        // 堆排序（大根堆），时间复杂度O(N*logN)，空间复杂度O(N)，不稳定
        // heapSort(arr);
        // 希尔排序，时间复杂度O(N*logN)，空间复杂度O(1)，不稳定
        // shellSort(arr);
        // 基数排序，时间复杂度O(C*N)，C为2*(数值长度+1)，空间复杂度O(K+N)，K为数值长度，稳定
        // baseSort(arr);
        return arr;
    }
    
    private void quickSort (int[] arr, int left, int right) {
        if (left < right) {
            int idx = partition(arr, left, right);
            quickSort(arr, left, idx - 1);
            quickSort(arr, idx + 1, right);
        }
    }
    
    private int partition (int[] arr, int left, int right) {
        int mark = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= mark) {
                right--;
            }
            if (left < right) {
                arr[left++] = arr[right];
            }
            while (left < right && arr[left] <= mark) {
                left++;
            }
            if (left < right) {
                arr[right--] = arr[left];
            }
        }
        arr[left] = mark;
        return left;
    }
    
    
    private void mergeSort (int[] arr) {
        int[] tmp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, tmp);
    }
    
    private void mergeSort (int[] arr, int left, int right, int[] tmp) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(arr, left, mid, tmp);
            mergeSort(arr, mid + 1, right, tmp);
            merge(arr, left, right, tmp);
        }
    }
    
    private void merge(int[] arr, int left, int right, int[] tmp) {
        int mid = left + (right - left) / 2, i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            tmp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            tmp[k++] = arr[i++];
        }
        while (j <= right) {
            tmp[k++] = arr[j++];
        }
        k = 0;
        while (left <= right) {
            arr[left++] = tmp[k++];
        }
    }
    
    private void heapSort (int[] arr) {
        int len = arr.length, buildMaxHeapLoopLimit = arr.length / 2;
        for (int i = buildMaxHeapLoopLimit; i >= 0; i--) {
            heapify(arr, i, len);
        }
        for (int i = len - 1; i > 0; i--) {
            swap(arr, i, 0);
            len--;
            heapify(arr, 0, len);
        }
    }
    
    private void heapify (int[] arr, int cur, int len) {
        int left = 2 * cur + 1, right = 2 * cur + 2, maxIdx = cur;
        if (left < len && arr[left] > arr[maxIdx]) {
            maxIdx = left;
        }
        if (right < len && arr[right] > arr[maxIdx]) {
            maxIdx = right;
        }
        if (cur != maxIdx) {
            swap(arr, cur, maxIdx);
            heapify(arr, maxIdx, len);
        }
    }
    
    
    private void shellSort(int[] arr) {
        for (int step = arr.length / 2; step >= 1; step /= 2) {
            for (int i = step, tmp, j; i < arr.length; i++) {
                tmp = arr[i];
                j = i - step;
                while (j >= 0 && arr[j] > tmp) {
                    arr[j + step] = arr[j];
                    j -= step;
                }
                arr[j + step] = tmp;
            }
        }
    }
    
    
    private void baseSort (int[] arr) {
        List<List<Integer>> bucketList = new ArrayList<>();
        // 建立0-9，共10个桶
        int baseCount = 10, numSize = 10;
        for (int i = 0; i < baseCount; i++) {
            bucketList.add(new ArrayList<>());
        }
        for (int i = 0; i < numSize; i++) {
            for (int num : arr) {
                bucketList.get(getBaseNum(num, i)).add(num);
            }
            int j = 0;
            for (List<Integer> bucket : bucketList) {
                for (Integer num : bucket) {
                    arr[j++] = num;
                }
                bucket.clear();
            }
        }
        // 负数的存在，需使用正/负数桶
        List<Integer> posBucket = bucketList.get(0), negBucket = bucketList.get(1);
        for (int num : arr) {
            if (num > 0) {
                posBucket.add(num);
            } else {
                negBucket.add(num);
            }
        }
        int idx = 0;
        for (int i = negBucket.size() - 1; i >= 0; i--) {
            arr[idx++] = negBucket.get(i);
        }
        for (Integer num : posBucket) {
            arr[idx++] = num;
        }
    }
    
    private int getBaseNum (int val, int count) {
        val = Math.abs(val);
        for (int i = 0; i < count; i++) {
            val /= 10;
        }
        return val %= 10;
    }
    
    
    private void swap (int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}

class Solution:
    def MySort(self , arr ):
        # write code here
        arr=sorted(arr)
        return arr

#include <errno.h>
// =================== The begin of function prototype  ==================
// 归并排序的入口 (Main Entry Point)
void merge_sort(const void* __base,
                const size_t __nmemb,
                const size_t __size,
                int (*__cmp) (const void* a, const void* b));

void m_sort(const void* __base, 
            const void* __tmp_base,
            int l, int r,
            const size_t __size,
            int (*__cmp) (const void* a, const void* b));

void merge(const void* __base,
           const void* __tmp_base,
           int l, int mid, int r,
           const size_t __size,
           int (*__cmp) (const void* a, const void* b));
// =================== The end of function prototype ==================

int compare_int(const void* a, const void* b) {
  return *(int*) a - *(int*) b;
}

int* MySort(int* arr, int arrLen, int* returnSize) {
  merge_sort(arr, arrLen, sizeof(int), compare_int);
  *returnSize = arrLen;
  return arr;
}

void merge_sort(const void* __base, 
                const size_t __nmemb,
                const size_t __size,
                int (*__cmp) (const void* a, const void* b)) {
  
  void* __tmp_base = malloc(__nmemb * __size);
  if (!__tmp_base) {
    printf("merge_sort memory overflow: %s\n", strerror(errno));
    return;
  }
  
  m_sort(__base, __tmp_base, 0, __nmemb - 1, __size, __cmp);
  free(__tmp_base);
}

void m_sort(const void* __base,
            const void* __tmp_base,
            int l, int r,
            const size_t __size,
            int (*__cmp) (const void* a, const void* b)) {
  
  // recursion exit condition
  if (l >= r) return;
  
  int mid = l + ((r - l) >> 1);
  m_sort(__base, __tmp_base, l, mid, __size, __cmp);
  m_sort(__base, __tmp_base, mid + 1, r, __size, __cmp);
  merge(__base,  __tmp_base, l, mid,  r, __size, __cmp);
}

void merge(const void* __base,
           const void* __tmp_base,
           int l, int mid, int r,
           const size_t __size,
           int (*__cmp) (const void* a, const void* b)) {

  int i = l, j = mid + 1, k = l;
  while (i <= mid && j <= r)
    if (__cmp((char*) __base + (i * __size), (char*) __base + (j * __size)) < 0)
      memcpy((char*) __tmp_base + (k++ * __size), (char*) __base + (i++ * __size), __size);
    else
      memcpy((char*) __tmp_base + (k++ * __size), (char*) __base + (j++ * __size), __size);
  
  while (i <= mid)
    memcpy((char*) __tmp_base + (k++ * __size), (char*) __base + (i++ * __size), __size);
  
  while (j <= r)
    memcpy((char*) __tmp_base + (k++ * __size), (char*) __base + (j++ * __size), __size);
  
  memcpy((char*) __base + (l * __size), (char*) __tmp_base + (l * __size), (r - l + 1) * __size);
}