時間複雑度から多O(nlogn)までの配列並べ替えを試みる

//    newSort()
vector newSort(vector &arr, int mina, int maxa){  
    vector sort(maxa - mina + 1);
    for(int i : arr) 
        sort[i - mina]++;
    
    vector res(arr.size());
    int index = 0;
    for(int i = 0; i < maxa - mina + 1; i++){
        if(sort[i]) {
            res[index++] = mina + i;
            sort[i--]--;
        }
    }
    return res;
}

//    
//           part()，       ，          ，        p，          p
int part(vector &arr, int low, int high){
    int p = arr[low];
    while(low < high) {
        while(low < high && arr[high] >= p) high--;
        arr[low] = arr[high];
        while(low < high && arr[low] <= p) low++;
        arr[high] = arr[low];
    }
    arr[low] = p;
    return low;
}

vector quickSort(vector &arr, int low, int high){
    if(low < high) {
        int pos = part(arr, low, high);//  
        quickSort(arr, low, pos - 1);
        quickSort(arr, pos + 1, high);
    }
    return arr;
}

//    
vector mixSort(vector &arr){
    //  1
    int mina = arr[0], maxa = arr[0];
    int n = arr.size();
    for(int i : arr) {
        mina = mina > i ? i : mina;
        maxa = maxa < i ? i : maxa;
    }
    //  2,3,4,   log 2  ；
    if(maxa - mina + 1 < n * log(n) / log(2)) return newSort(arr, mina, maxa);
    return quickSort(arr, 0, n - 1);//  
}

//    
int main(){
    vector a = {6, 9, 4, 2, 8, 6, 7, 3, 2, 5, 1};
    a = mixSort(a);
    for(int i : a) cout << i << ' ';
    return 0;
}