数组归并为单个元素的最小成本自研算法正确性验证

问题背景 #

给定包含N个元素的无序数组，每次可合并任意两个元素为一个，合并成本等于两个元素的取值之和，要求计算将所有元素合并为单个时的最小总成本。

示例：
给定数组 A = [1,2,3,4]
第一步选择1和2合并，成本为1+2=3，此时数组变为[3,3,4]，累计成本为3。
第二步选择两个3合并，成本为3+3=6，此时数组变为[4,6]，累计成本为9。
第三步选择4和6合并，成本为4+6=10，此时数组仅剩[10]，累计总成本为19。

该问题的经典解法核心是每次选取当前最小的两个元素合并，通常用最小堆实现，取最小元素时间复杂度O(1)，插入新元素复杂度O(log n)，整体时间复杂度O(n log n)。

自研方案说明 #

我设计了另一种思路，暂未找到反例：我认为每次选取的两个最小元素的和，一定大于此前所有合并得到的和，因此存储合并和的temp数组天然有序，可以通过双指针O(1)获取当前最小元素。
该算法先对输入数组排序，再通过双指针分别遍历原有序数组和有序temp数组选取最小两个元素合并，时间复杂度同样为O(n log n)，实现代码如下：

int minCost(vector<int>& arr) {
    sort(arr.begin(), arr.end());
    // temp数组存储每次合并得到的元素和
    vector<int> temp;
    // 原有序数组的遍历指针
    int i = 0;
    // temp数组的遍历指针
    int j = 0;
    int cost = 0;

    // 只要两个数组剩余元素总数大于1就继续合并
    while(arr.size() - i + temp.size() - j > 1) {
        int num1, num2;
        // 选取第一个最小元素
        if(i < arr.size() && j < temp.size()) {
            if(arr[i] <= temp[j])
                num1 = arr[i++];
            else
                num1 = temp[j++];
        }
        else if(i < arr.size())
            num1 = arr[i++];
        else if(j < temp.size())
            num1 = temp[j++];

        // 选取第二个最小元素
        if(i < arr.size() && j < temp.size()) {
            if(arr[i] <= temp[j])
                num2 = arr[i++];
            else
                num2 = temp[j++];
        }
        else if(i < arr.size())
            num2 = arr[i++];
        else if(j < temp.size())
            num2 = temp[j++];

        int sum = num1 + num2;
        temp.push_back(sum);
        cost += sum;
    }
    return cost;
}

疑问 #

请问这个自研算法是否正确？若不正确，我忽略了什么逻辑缺陷，以及存在哪些可以让算法失败的测试用例？该问题对应SPOJ平台REDARR2题。

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