思路：归并排序

先用merge函数把l到mid区间和mid+1到r区间排序，然后利用归并的思想结合compare函数解决。详见代码注释

时间复杂度分析：
T（N）=2*T（N/2）+O（N）
T（N）=O（NlogN）

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> merge(int l,int r,int N)//merge函数返回l到r区间已经排好序的vector容器
    {
        if (l == r)//递归出口，如果只有一个元素，直接把这个元素返回即可
        {
        vector<int>temp;
        temp.push_back(l);
        return temp;
        }
        int mid = (l + r) / 2;
        vector<int>a=merge(l,mid,N);//递归求解
        vector<int>b=merge(mid+1,r,N);
        vector<int>res;//res是一会要返回的容器
        int t1=0,t2=0;//t1和t2分别指向a和b容器中的元素
        int flag=0;
        while(t1<a.size()&&t2<b.size())
        {
            if(compare(a[t1],b[t2]))如果a中元素小，就把a中元素压入res中
            {
                res.push_back(a[t1++]);
            }
            else
            {
                res.push_back(b[t2++]);
            }
            if(t1>=a.size())//如果t1已经指向了a容器末尾，flag=1表示a已经遍历完全
            {
              flag=1;break;  
            }
            if(t2>=b.size())//同理
            {
                flag=2;break;
            }
        }
        if(flag==1)//把b中剩余元素压入res中
        {
            for(int i=t2;i<b.size();i++)
            {
                res.push_back(b[i]);
            }
        }
        else//同理
        {
            for(int i=t1;i<a.size();i++)
            {
                res.push_back(a[i]);
            }
        }
        return res;
    }
    vector<int> specialSort(int N) {
        vector<int>ans=merge(1,N,N);
        return ans;
    }
};