IT
分配ソートとは？カウント・基数・バケットの仕組みと計算量、実装・最適化ガイド
分配ソートとは — 概観 分配ソート（ぶんぱいソート、distribution sort）は、キーの値域や桁の構造を利用してデータを「分配（バケット／カウント）」し、その後に各グループを整理して全体をソートする一群の非比 […]
LSD法（基数ソート・下位桁優先）完全ガイド：仕組み・実装・計算量・注意点
LSD法とは — 基数ソートの「下位桁優先」アプローチ LSD法（Least Significant Digit 法）は、基数ソート（Radix Sort）の一種で、キーの「下位桁（最も重要度の低い桁）から上位桁へ順に処 […]
合併ソート（マージソート）完全ガイド：仕組み・計算量・実装と実務で使える最適化テクニック
合併ソートとは 合併ソート（マージソート、Merge Sort）は、比較ベースの安定な整列アルゴリズムの一つで、分割統治法（divide and conquer）を用いて配列やリストを整列します。配列を半分に分割してそれ […]
多路マージ（k-way マージ）入門：ヒープとルーザーツリーによる実装・外部ソートとLSMツリーの最適化
多路マージとは 多路マージ（たろ・マージ、k-way merge）は、複数（k個）の既にソートされた入力列を一つのソート済み列に統合するアルゴリズム群を指します。2路（2-way）マージがマージソートの典型的な一部である […]
k-wayマージ入門：計算量（O(N log k））からヒープ・敗者木実装、外部ソートとI/O最適化まで
k-wayマージとは何か k-wayマージ（k-way merge）は、k個のソート済みシーケンス（配列、リスト、ファイルなど）を一つのソート済みシーケンスに統合するアルゴリズム群の総称です。2-way（2つ）マージは古 […]
分割統治法とは：基本原理と漸近解析（マスター定理）・代表アルゴリズムと並列化／実装の実践ガイド
分割統治法とは — 概要と直感 分割統治法（ぶんかつとうちほう、divide and conquer）は、問題を小さな部分問題に分割し、それぞれを解いてから結果を結合して元の問題の解を得るアルゴリズム設計の基本パターンで […]
比較ソート徹底ガイド：代表アルゴリズム・計算量・安定性と最適な選び方
比較ソートとは 比較ソート（ひかくソート）とは、要素同士の「比較」操作（大小比較や順序比較）を基本操作として並べ替えを行うソートアルゴリズムの総称です。キーの大小関係を直接利用して順序を決定するため、取り扱えるキーは任意 […]
外部ソート完全ガイド：外部マージソートの仕組み・I/O最適化と実装ポイント
外部ソートとは — 大量データをディスクで効率的に並べ替える技術 外部ソート（がいぶソート、external sort）は、メインメモリ（RAM）に収まらないほど大きなデータ集合をディスク（外部記憶）を使ってソートするた […]
ボトムアップマージソート徹底解説：仕組み・擬似コード・実装最適化（トップダウン比較付き）
ボトムアップマージソートとは ボトムアップマージソート（bottom-up merge sort）は、マージソートの反復（イテレーティブ）版で、配列を段階的に小さなソート済みの塊（ラン）に分け、それらを長さ 1, 2, […]
自然マージソートとは？ラン検出で高速化する仕組み・計算量・実装最適化とTimsortの関係
自然マージソートとは — 概要 自然マージソート（Natural Merge Sort）は、配列やリスト内に既に存在する単調増加（あるいは単調減少）の「ラン（run）」を利用してソートを高速化するマージソートの変種です。 […]