(归并排序)

这是一道排序题， 需要注意的是 compare 函数只能调用10000次， 也就是说比较次数要少
那么在 排序算法中， 归并排序和堆排序的比较次数少，由于堆排序需要建堆，也需要比较
所以可以选择归并排序， C++ 中 std::stable_sort() 是使用 归并排序实现的

C++ 代码

// Forward declaration of compare API.
// bool compare(int a, int b);
// return bool means whether a is less than b.

class Solution {
public:
    vector<int> specialSort(int N) {
        vector<int> res;
        for (int i = 1; i <= N; i ++ ) res.push_back(i);
        stable_sort(res.begin(), res.end(), compare);
        return res;

    }
};