如何优化归并排序算法以通过在线判题的时间限制？

我正在完成大学作业，作业需通过在线判题系统测试，运行时间过长会触发时间限制。试过冒泡、快速、插入、归并排序，最终选了时间复杂度O(NlogN)的稳定排序——归并排序，但还是超时。

我的归并排序代码 #

void merge(vector<Order>& orderVector, int low, int high, int mid)
{
    int i, j, k;
    vector<Order> c(orderVector.size(), orderVector.at(0));
    i = low;
    k = low;
    j = mid + 1;
    while (i <= mid && j <= high) {
        if ((orderVector.at(i).selection_time < orderVector.at(j).selection_time) || (orderVector.at(i).selection_time == orderVector.at(j).selection_time && orderVector.at(i).shipping_time < orderVector.at(j).shipping_time)) {
            c.at(k) = orderVector.at(i);
            k++;
            i++;
        }
        else  {
            c.at(k) = orderVector.at(j);
            k++;
            j++;
        }
    }
    while (i <= mid) {
        c.at(k) = orderVector.at(i);
        k++;
        i++;
    }
    while (j <= high) {
        c.at(k) = orderVector.at(j);
        k++;
        j++;
    }
    for (i = low; i < k; i++)  {
        orderVector.at(i) = c.at(i);
    }
}

void sort(vector<Order>& orderVector, int low, int high)
{
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        sort(orderVector, low, mid);
        sort(orderVector, mid + 1, high);
        merge(orderVector, low, high, mid);
    }
}

数据读取与输出代码 #

int main(int argc, char *argv[]){
    string data;
    getline(cin, data);
   
    vector<string> data_v = split(data, "; ", numeric_limits<size_t>::max());

    vector<Order> orderVector;

    for(string d : data_v){
        Order *orders = new Order(id, selection, shipping);

        orderVector.push_back(*orders);
    }

    sort(orderVector, 0, orderVector.size() - 1);

    for(long unsigned int i = 0; i < orderVector.size(); i++)
    {
        cout << orderVector.at(i).id << " ";
    }

    cout << endl;
}

注：移除了大学提供的基础模板，Order类的实际数据填充代码未展示，不影响效率分析。

性能瓶颈分析与优化点 #

1. 临时容器空间浪费严重 #

每次merge都创建和原vector一样大的临时容器c，内存分配和初始化的开销极大。应该只创建当前low到high区间所需的空间，减少内存操作。

2. at()方法的额外开销 #

at()会做边界检查，相比直接用[]运算符，高频访问下累积的开销会拖慢速度，排序场景下可以直接用[]。

3. main函数中的冗余操作 #

• 用new Order后push_back(*orders)，既造成内存泄漏，又多了一次对象拷贝，直接构造对象插入更高效。
• 没有提前给vector预留空间，push_back会频繁触发扩容和拷贝。

4. IO效率低下 #

循环逐个cout输出，加上endl强制刷新缓冲区，IO开销很大。关闭cin/cout同步、用'\n'代替endl可以大幅提速。

5. 递归与小数据量处理 #

归并排序的递归有一定开销，小数据量下插入排序的常数项更低，可以设置阈值（比如16），区间小于阈值时切换到插入排序。

修改后的代码示例 #

优化后的merge函数 #

void merge(vector<Order>& orderVector, int low, int high, int mid)
{
    int i = low, j = mid + 1, k = 0;
    // 仅分配当前区间所需的空间
    vector<Order> c(high - low + 1);

    while (i <= mid && j <= high) {
        if ((orderVector[i].selection_time < orderVector[j].selection_time) || 
            (orderVector[i].selection_time == orderVector[j].selection_time && orderVector[i].shipping_time < orderVector[j].shipping_time)) {
            c[k++] = orderVector[i++];
        } else {
            c[k++] = orderVector[j++];
        }
    }

    while (i <= mid) c[k++] = orderVector[i++];
    while (j <= high) c[k++] = orderVector[j++];

    // 拷贝回原区间
    for (k = 0; k < c.size(); ++k) {
        orderVector[low + k] = c[k];
    }
}

优化后的main函数 #

int main(int argc, char *argv[]){
    // 关闭cin/cout同步，加速IO
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string data;
    getline(cin, data);
   
    vector<string> data_v = split(data, "; ", numeric_limits<size_t>::max());

    vector<Order> orderVector;
    // 提前预留空间，避免扩容拷贝
    orderVector.reserve(data_v.size());

    for(string& d : data_v){
        // 直接在vector中构造对象，避免拷贝
        orderVector.emplace_back(id, selection, shipping);
    }

    sort(orderVector, 0, orderVector.size() - 1);

    // 批量输出，减少IO调用
    for(size_t i = 0; i < orderVector.size(); ++i)
    {
        if(i != 0) cout << ' ';
        cout << orderVector[i].id;
    }
    // 用'\n'代替endl，避免强制刷新缓冲区
    cout << '\n';
}

可选：混合排序（归并+插入） #

// 插入排序实现
void insertionSort(vector<Order>& arr, int low, int high) {
    for (int i = low + 1; i <= high; ++i) {
        Order temp = arr[i];
        int j = i - 1;
        while (j >= low && 
               (arr[j].selection_time > temp.selection_time || 
                (arr[j].selection_time == temp.selection_time && arr[j].shipping_time > temp.shipping_time))) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = temp;
    }
}

// 修改后的sort函数
void sort(vector<Order>& orderVector, int low, int high) {
    const int THRESHOLD = 16;
    // 小数据量用插入排序
    if (high - low + 1 <= THRESHOLD) {
        insertionSort(orderVector, low, high);
        return;
    }
    // 用low + (high-low)/2避免low+high溢出
    int mid = low + (high - low)/2;
    sort(orderVector, low, mid);
    sort(orderVector, mid + 1, high);
    merge(orderVector, low, high, mid);
}

内容的提问来源于stack exchange，提问作者Fernando Goncalves