2026-10-17
merge_logs.c
#include <stdio.h>
static void merge(const char *a[], int na, const char *b[], int nb, const char *out[]) {
int i = 0, j = 0, k = 0;
while (k < na + nb) {
bool take_a = j == nb || (i < na && a[i][0] < b[j][0]);
out[k++] = take_a ? a[i++] : b[j++];
}
}
int main(void) {
const char *a[] = {"1 boot", "3 disk"};
const char *b[] = {"1 auth", "2 net", "3 fan"};
const char *out[5];
merge(a, 2, b, 3, out);
for (int k = 0; k < 5; k++) {
puts(out[k]);
}
}
merge は、日付の昇順に並んだ2つのログ a と b を、日付の昇順の1本にまとめるつもりの関数です。日付は各行の先頭の数字で、同じ日付の行どうしは、古いログ a の行を b の行より先に置く約束です。入力は main の a と b です。いまは 1 auth、1 boot、2 net、3 fan、3 disk の順に5行が出ます。本来の出力は 1 boot、1 auth、2 net、3 disk、3 fan の順です。
Answer
Wrong
bool take_a = j == nb || (i < na && a[i][0] < b[j][0]);
日付が同じ行どうしを比べると、a[i][0] < b[j][0] は偽になり、take_a も偽になるので b の行が先に書かれます。1 boot と 1 auth では 1 auth が、3 disk と 3 fan では 3 fan が先に出て、同じ日付の中だけ a と b の順が逆になります。日付の昇順は崩れないので、出力を眺めただけでは気付きにくい欠陥です。
Right
bool take_a = j == nb || (i < na && a[i][0] <= b[j][0]);
<= にすると、日付が等しいときも a の行を取ります。a の行は、同じ日付の b の行がまだ残っていても先に出ていくので、同じ日付の中では a の行がすべて b の行より前に並びます。マージソート(merge sort)が安定ソートになるのも、半分ずつ並べた列を併合するときに、等しければ前半の列の要素を取るからです。この比較が < だと、マージソートは等しい要素の順を保てなくなります1。
- C++ の
std::mergeは、2つの範囲に同値な要素があるとき、1つ目の範囲の要素を先に置くと規定しています。std::stable_sortをマージソートで実装する処理系も、この規則で併合しています。