TimSort内存优化：2200万级元素排序内存超限问题求解

你的TimSort实现处理超大元素量时内存超限，核心原因是merge函数每次合并都会动态分配两个临时数组L和R，频繁的内存分配不仅导致峰值内存超标，还会产生内存碎片、降低运行效率。调整RUN大小无法解决该问题，因为内存占用的核心矛盾在merge阶段的临时内存分配逻辑。

核心优化方案：复用临时缓冲区+仅复制短段子数组 #

预先分配一个足够大的临时缓冲区，在所有merge操作中复用，同时合并时仅复制较短的子数组到临时空间，将临时内存需求从n1+n2降至min(n1,n2)，大幅降低峰值内存占用。

修改后的完整代码 #

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct funkc {
    int id;
    int punkty;
};

void insertSort(funkc arr[], int left, int right) {
    for (int i = left + 1; i <= right; i++) {
        funkc key = arr[i];
        int j = i - 1;
        while (j >= left && arr[j].punkty > key.punkty) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

// 复用临时缓冲区，仅复制较短的子数组以减少内存占用
void merge(funkc arr[], int left, int mid, int right, vector<funkc>& temp) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    if (n1 <= n2) {
        // 复制左段到临时缓冲区
        copy(arr + left, arr + mid + 1, temp.begin());
        int i = 0, j = mid + 1, k = left;
        // 合并到原数组
        while (i < n1 && j <= right) {
            if (temp[i].punkty <= arr[j].punkty) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = arr[j++];
            }
        }
        // 复制剩余的左段元素
        while (i < n1) {
            arr[k++] = temp[i++];
        }
    } else {
        // 复制右段到临时缓冲区
        copy(arr + mid + 1, arr + right + 1, temp.begin());
        int i = mid, j = n2 - 1, k = right;
        // 从后往前合并，避免覆盖未处理元素
        while (i >= left && j >= 0) {
            if (arr[i].punkty >= temp[j].punkty) {
                arr[k--] = arr[i--];
            } else {
                arr[k--] = temp[j--];
            }
        }
        // 复制剩余的右段元素
        while (j >= 0) {
            arr[k--] = temp[j--];
        }
    }
}

void timSort(funkc arr[], int n) {
    const int RUN = 32;
    // 预先分配最大需要的临时空间：最多为n/2（合并两个等长子数组时，较短子数组长度为n/2）
    vector<funkc> temp(n / 2);

    // 对每个RUN段执行插入排序
    for (int i = 0; i < n; i += RUN) {
        insertSort(arr, i, min(i + RUN - 1, n - 1));
    }

    // 逐步合并RUN段
    for (int size = RUN; size < n; size *= 2) {
        for (int left = 0; left < n; left += 2 * size) {
            int mid = left + size - 1;
            int right = min(left + 2 * size - 1, n - 1);
            if (mid < right) {
                merge(arr, left, mid, right, temp);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); // 加速IO操作

    int n = 0;
    cin >> n ;
    funkc* arr = new funkc[n];
    for (int i = 0; i < n; i++){
        arr[i].id = i;
        arr[i].punkty = rand() % 1000001;
    }

    timSort(arr, n);

    for (int i = 0; i < n; i++) {
        cout << arr[i].punkty << " ";
    }
    cout << endl;

    delete[] arr;
    return 0;
}

优化效果说明 #

1. 内存占用减半：原实现峰值内存为原数组大小+临时数组总大小（接近2倍原数组），优化后仅需原数组大小+n/2的临时缓冲区，直接将峰值内存降低约50%。
2. 效率提升：避免了频繁的new/delete操作，减少内存碎片的同时降低了内存分配的性能开销。

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