我的 MergeSort 有什么问题？

Question

#include <cstring>
#include <stdint.h>
#include <algorithm>
#include <ctime>
#include <iostream>
#include <cstdlib>


using namespace std;

int array[1000];
int temp[1000];

void mergeSort(int start, int count) {
    if(count == 1) {
        return;
    }
    int startFirst = start;
    int countFirst = count/2;
    int startSecond = startFirst + countFirst;
    int countSecond = count - countFirst;
    mergeSort(startFirst, countFirst);
    mergeSort(startSecond, countSecond);        
    int refFirst = 0;
    int refSecond = 0;
    for(int i = start; i < start + count; i++){
        if(refFirst == countFirst || array[startSecond + refSecond] < array[startFirst + refFirst]) {
            temp[i] = array[startSecond + refSecond];
            refSecond++;
        } else {
            temp[i] = array[startFirst + refFirst];
            refFirst++;
        }
    }
    memcpy(array + start, temp + start, count*sizeof(int));
}

int main() {
    for(int i = 0; i <1000; i++){
        array[i] = 1000 - i;
    }
    mergeSort(0, 1000);
    for(int i =0; i <1000; ++i){
        cout << array[i] << " ";
    }
    cout << endl;
    return 0;
}

我使用两个数组编写了一个简单的 MergeSort 实现，它输出垃圾：

1 2 3 2 5 4 4 3 9 8 8 7 8 7 6 5 17 16 16 15 16 15 14 13 16 15 14 13 12 11 10 9 33 32 32 31 32 31 30 29 32 31 30 29 28 27 26 25 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 64 63 63 62 63 62 61 60 63 62 61 60 59 58 57 56 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 126 125 125 124 125 124 123 122 125 124 123 122 121 120 119 118 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 251 250 250 249 250 249 248 247 250 249 248 247 246 245 244 243 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 1 2 3 2 5 4 4 3 9 8 8 7 8 7 6 5 17 16 16 15 16 15 14 13 16 15 14 13 12 11 10 9 33 32 32 31 32 31 30 29 32 31 30 29 28 27 26 25 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 64 63 63 62 63 62 61 60 63 62 61 60 59 58 57 56 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 126 125 125 124 125 124 123 122 125 124 123 122 121 120 119 118 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 108 107 106 105 104 103 102 101 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 65 64 251 250 250 249 250 249 248 247 250 249 248 247 246 245 244 243 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 250 249 248 247 246 245 244 243 242 241 240 239 238 237 236 235 234 233 232 231 230 229 228 227 226 225 224 223 222 221 220 219 218 217 216 215 214 213 212 211 210 209 208 207 206 205 204 203 202 201 200 199 198 197 196 195 194 193 192 191 190 189 188 187 186 185 184 183 182 181 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126

Answer 1

还需要检查 refSecond != countSecond。短路评估应该消除对 && 的一组额外括号的需要。

        if(refFirst == countFirst || refSecond != countSecond
            && array[startSecond + refSecond] < array[startFirst + refFirst]) {
            temp[i] = array[startSecond + refSecond];
            refSecond++;
        } else {
            temp[i] = array[startFirst + refFirst];
            refFirst++;
        }

Answer 2

合并数组时，您应该只在第二个数组未用完时从中写入。您应该将 array[startSecond + refSecond] < array[startFirst + refFirst] 替换为 (refSecond != countSecond && array[startSecond + refSecond] < array[startFirst + refFirst])

我的 MergeSort 有什么问题？

What's wrong with my MergeSort?

c++

sorting

mergesort