30604：稳定归并排序

题目

按 key 对记录排序，并在键相等时保持 payload 的输入相对顺序。

解析

先分配临时数组；分配成功后才允许改写输入。每次合并两个已经有序的区间时，若两侧键相等，优先复制左侧记录，这个选择正是稳定性的来源。比较只用 < 和 <=，不能用键相减。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int64_t key;
    uint64_t payload;
} SortRecord;

bool stable_merge_sort_records(
    SortRecord *items,
    size_t count
) {
    if (count == 0) {
        return true;
    }
    if (items == NULL || count > SIZE_MAX / sizeof *items) {
        return false;
    }
    SortRecord *temporary = malloc(count * sizeof *temporary);
    if (temporary == NULL) {
        return false;
    }

    size_t width = 1;
    while (width < count) {
        size_t left = 0;
        while (left < count) {
            size_t middle = width > count - left
                ? count
                : left + width;
            size_t remaining = count - middle;
            size_t right = width > remaining
                ? count
                : middle + width;
            size_t first = left;
            size_t second = middle;
            size_t output = left;
            while (first < middle && second < right) {
                if (items[first].key <= items[second].key) {
                    temporary[output++] = items[first++];
                } else {
                    temporary[output++] = items[second++];
                }
            }
            while (first < middle) {
                temporary[output++] = items[first++];
            }
            while (second < right) {
                temporary[output++] = items[second++];
            }
            memcpy(
                items + left,
                temporary + left,
                (right - left) * sizeof *items
            );
            if (right == count) {
                break;
            }
            left = right;
        }
        if (width > count / 2) {
            break;
        }
        width *= 2;
    }
    free(temporary);
    return true;
}

每一轮扫描所有记录，每轮宽度至少翻倍，故时间复杂度为 $O(n\log n)$，临时数组占用 $O(n)$ 空间。