Jerry の言う通り、気になるのが Ctrl-C だけなら、一度に一定期間 SIGINT を無視することができます。一般的にプロセスの死に対して証明したい場合は、何らかの最小限のジャーナリングが必要です。2 つの要素を交換するには:
1) ファイルの末尾または別のファイルの制御構造にレコードを追加し、ファイルのどの 2 つの要素 A と B を交換するかを示します。
2) A をスクラッチ スペースにコピーし、コピーしたことを記録して、フラッシュします。
3) B を A の上にコピーし、コピーしたことをスクラッチ スペースに記録し、フラッシュします。
4) B 上のスクラッチ スペースからコピーします。
5) レコードを削除します。
これは、すべての実用的な目的で O(1) の余分なスペースであるため、ほとんどの定義ではインプレースとしてカウントされます。理論的には、n を任意に大きくできる場合、インデックスを記録すると O(log n) になります。実際には、これは非常に小さい log n であり、合理的なハードウェア/実行時間により、64 より上に制限されます。
すべての場合において、「フラッシュ」と言うときは、変更を「十分に」コミットすることを意味します。基本的なフラッシュ操作では、プロセス内のバッファーのみをフラッシュすることがありますが、実際には物理メディアを同期しません。これは、OS/デバイス ドライバー/ハードウェア レベル全体でバッファーをフラッシュしないためです。プロセスの停止だけを心配している場合はこれで十分ですが、突然のメディアのマウント解除が心配な場合は、ドライバーをフラッシュする必要があります。停電が心配な場合は、ハードウェアを同期する必要がありますが、そうではありません。UPS を使用している場合、または停電が非常にまれで、データが失われても構わないと思う場合は、それで問題ありません。
起動時に、「スワップ進行中」のレコードがないかスクラッチ スペースを確認します。見つかった場合は、どこまで到達したかを調べ、そこからスワップを完了して、データを健全な状態に戻します。次に、並べ替えをやり直します。
以前の 2 倍のレコードの書き込みを行っており、フラッシュ/同期には驚くほどコストがかかる可能性があるため、ここには明らかにパフォーマンスの問題があります。実際には、インプレースソートには、多くのスワップを伴う複合的な移動操作が含まれる場合がありますが、すべての要素がスクラッチスペースにヒットするのを回避するために最適化できます。データを上書きする前に、そのコピーを安全な場所に保管し、各要素のコピーが 1 つだけ含まれる状態にファイルを戻すために、そのコピーの保存先を記録しておく必要があります。
Jerry の言うとおり、真のインプレース ソートはほとんどの実用的な目的には難しすぎて時間がかかりすぎます。元のファイル サイズの線形分数をスクラッチ スペースとして確保できる場合は、マージ ソートを使用する方がはるかに効率的です。
明確化に基づいて、インプレースソートを使用してもフラッシュ操作は必要ありません。異常終了後の起動時に復元するのではなく、終了する前にデータを安全に取得するために SIGINT ハンドラーがアクセスできる、同じように機能するメモリ内のスクラッチ スペースが必要であり、シグナルでそのメモリにアクセスする必要があります。安全な方法 (技術的には、どの変更が行われたかを示すフラグを使用することを意味します)。それでも、真のインプレースソートよりもマージソートを使用したほうがよいでしょう。sig_atomic_t