# 機能設計書 20-配列ソート

## 概要

本ドキュメントは、Julia言語における配列ソート機能の設計を記述する。sort / sort! / sortperm / partialsort などのソートアルゴリズムを提供する。

### 本機能の処理概要

Sortモジュールは、配列やコレクションの要素をさまざまなアルゴリズムとオーダリングで並び替えるソート機能を提供する。InsertionSort、ScratchQuickSort、RadixSort、CountingSort等の複数のアルゴリズムを組み合わせた適応型ソートパイプラインにより、入力データの特性に応じた最適なアルゴリズムを自動選択する設計となっている。

**業務上の目的・背景**：配列やコレクションのソートは、データ処理・検索・集計などのあらゆる場面で基本となる操作である。汎用的なソート関数群を提供し、安定性・性能・メモリ効率のバランスを取りながら、カスタムの比較関数やキー抽出関数によるソートもサポートする。ソート済み配列に対する二分探索（searchsorted系関数）も併せて提供し、効率的なデータ検索を可能にする。

**機能の利用シーン**：（1）配列のソート（sort/sort!）、（2）ソート順の置換ベクトル取得（sortperm/sortperm!）、（3）部分ソート（partialsort/partialsort!）、（4）ソート済み配列への二分探索（searchsorted/searchsortedfirst/searchsortedlast）、（5）ソート済み確認（issorted）、（6）多次元配列の次元指定ソート、（7）NTupleのソート。

**主要な処理内容**：
1. sort!/sort関数による1次元配列のソート
2. sort!/sort関数による多次元配列の次元指定ソート
3. sortperm/sortperm!関数によるソート置換ベクトルの取得
4. partialsort!/partialsort関数による部分ソート
5. searchsorted/searchsortedfirst/searchsortedlast/insortedによる二分探索
6. issorted関数によるソート済み判定
7. InitialOptimizations適応型パイプライン（SubArrayOptimization, MissingOptimization, BoolOptimization, IEEEFloatOptimization）
8. DefaultStable/DefaultUnstableアルゴリズム選択（IsUIntMappable分岐、CountingSort、RadixSort、ScratchQuickSort等）

**関連システム・外部連携**：Base.Order（Ordering, ord, lt等の順序定義）。AbstractArray/SubArray（ビュー最適化）。

**権限による制御**：特になし。

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| 2 | Juliaプロンプト（julia>） | 参照画面 | REPL上でソート操作を実行 |

## 機能種別

計算処理（配列ソートアルゴリズム）/ データ操作（二分探索・置換）

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| v | AbstractVector{T} | Yes | ソート対象の配列 | - |
| alg | Algorithm | No | ソートアルゴリズム（デフォルト: defalg(v)） | Algorithm型 |
| lt | Function | No | 比較関数（デフォルト: isless） | strict weak order |
| by | Function | No | キー抽出関数（デフォルト: identity） | callable |
| rev | Bool/Nothing | No | 逆順フラグ（デフォルト: nothing） | - |
| order | Ordering | No | 順序オブジェクト（デフォルト: Forward） | Ordering型 |
| scratch | Vector{T}/Nothing | No | スクラッチスペース（デフォルト: nothing） | 同一eltype |
| dims | Integer | No（多次元の場合Yes） | ソート次元（多次元配列用） | 1 <= dims <= ndims(A) |
| k | Integer/OrdinalRange | Yes（partialsort） | 部分ソート対象インデックス | 範囲内 |

### 入力データソース

Julia式からの直接入力。sort!/sort/sortperm/partialsort等の関数呼び出し。

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| sorted_vector | AbstractVector{T} | ソート済み配列（sort!はin-place、sortはコピー） |
| permutation | Vector{Int} | ソート置換ベクトル（sortperm） |
| partial_result | T/SubArray | 部分ソート結果（partialsort） |
| search_range | UnitRange{Int} | 二分探索結果範囲（searchsorted） |
| search_index | Int | 二分探索結果インデックス（searchsortedfirst/last） |
| is_sorted | Bool | ソート済み判定結果（issorted） |

### 出力先

メモリ上の結果オブジェクトとして返却。sort!はin-placeで入力配列を変更。

## 処理フロー

### 処理シーケンス

```
1. sort!呼び出し
   └─ alg選択: defalg(v) でデフォルトアルゴリズム決定
   └─ ord(lt, by, rev, order) でOrdering構築
   └─ maybe_apply_initial_optimizations(alg) で最適化ラッパー適用
   └─ _sort!(v, alg, order, kw) でソート実行

2. InitialOptimizations パイプライン
   └─ SubArrayOptimization: SubArrayをunwrap（パフォーマンス向上）
   └─ MissingOptimization: Missing値を末尾に移動
   └─ BoolOptimization: Bool配列の特殊処理（カウントのみ）
   └─ Small{10}: 10要素以下はInsertionSort
   └─ IEEEFloatOptimization: NaN末尾移動+符号分割+UInt変換

3. DefaultStable/DefaultUnstable パイプライン
   └─ IsUIntMappable分岐
       ├─ Yes: Small{40} → CheckSorted → ComputeExtrema → ConsiderCountingSort → ConsiderRadixSort → Small{80} → ScratchQuickSort
       └─ No: StableCheckSorted → ScratchQuickSort

4. 二分探索（searchsorted系）
   └─ AbstractRange最適化（O(1)計算）
   └─ 一般AbstractVector向け二分探索（O(log n)）
```

### フローチャート

```mermaid
flowchart TD
    A["sort!(v; alg, lt, by, rev, order)"] --> B[defalg: アルゴリズム選択]
    B --> C[InitialOptimizations]
    C --> D[SubArrayOptimization]
    D --> E[MissingOptimization]
    E --> F[BoolOptimization]
    F --> G{length <= 10?}
    G -->|Yes| H[InsertionSort]
    G -->|No| I[IEEEFloatOptimization]
    I --> J{UIntMappable?}
    J -->|Yes| K{length <= 40?}
    K -->|Yes| H
    K -->|No| L[CheckSorted]
    L --> M[ComputeExtrema]
    M --> N{CountingSort適用可?}
    N -->|Yes| O[CountingSort]
    N -->|No| P{RadixSort適用可?}
    P -->|Yes| Q[RadixSort]
    P -->|No| R{length <= 80?}
    R -->|Yes| H
    R -->|No| S[ScratchQuickSort]
    J -->|No| T[StableCheckSorted]
    T --> S
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | デフォルトアルゴリズム選択 | Number/Missingの場合DEFAULT_UNSTABLE、それ以外はDEFAULT_STABLE | defalg呼び出し時 |
| BR-02 | 安定ソート保証 | DEFAULT_STABLEは等値要素の順序を保持 | 安定ソート指定時 |
| BR-03 | strict weak order | lt関数は非反射的・非対称・推移的でなければならない | 全sort呼び出し |
| BR-04 | Missing値の処理 | Missing値はDirectOrderingで末尾に配置 | Missing含む配列 |
| BR-05 | NaN値の処理 | NaN値はIEEEFloatOptimizationで末尾に移動 | Float配列 |
| BR-06 | Bool配列最適化 | Bool配列はカウントベースでO(n)ソート | Bool配列 |
| BR-07 | SMALL_THRESHOLD | 20要素以下でScratchQuickSortからInsertionSortに切替 | ScratchQuickSort内 |
| BR-08 | 逆順検出 | 500要素以上で逆順検出を実施、検出時にreverse! | CheckSorted内 |
| BR-09 | CountingSort条件 | 値域が配列長の半分未満の場合に適用 | 整数配列 |
| BR-10 | Tuple特殊処理 | 9要素以下のNTupleはアンロールmergesort | NTupleソート時 |

### 計算ロジック

- InsertionSort: O(n^2)最悪ケース、O(n)ベストケース（ほぼソート済み）、安定、in-place
- ScratchQuickSort: O(n log n)平均、O(n^2)最悪（極めて稀）、安定、スクラッチスペース使用
- CountingSort: O(n + k)（kは値域幅）、安定、追加メモリO(k)
- RadixSort: O(n * b/w)（bはビット数、wはチャンクサイズ）、安定、追加メモリO(n)
- 二分探索: O(log n)、AbstractRangeに対してはO(1)最適化
- partition!: ハッシュベースのピボット選択（mod(hash(lo), lo:hi)）

## データベース操作仕様

該当なし

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| - | ArgumentError | dims が次元範囲外 | 1 <= dims <= ndims(A) を指定 |
| - | ArgumentError | sortperm!でix/vのaxesが不一致 | 同じaxesのインデックスベクトルを使用 |
| - | ArgumentError | scratchのeltypeが不一致 | 同じeltypeのスクラッチスペースを使用 |
| - | MethodError | lt関数がstrict weak orderでない | 正しい比較関数を指定 |

### リトライ仕様

該当なし

## トランザクション仕様

該当なし

## パフォーマンス要件

- 適応型アルゴリズム選択: 入力データの特性（型、サイズ、値域、ソート済み度合い）に応じて最適なアルゴリズムを自動選択
- InitialOptimizations: Missing/NaN/Bool等の特殊値に対する前処理でO(n)のオーバーヘッドのみ
- 小規模配列（10要素以下）: InsertionSortへの早期ディスパッチでオーバーヘッド最小化
- SMALL_THRESHOLD = 20: ScratchQuickSortの再帰ベースケースとしてInsertionSort使用
- ScratchQuickSort: スクラッチスペースを使用してキャッシュ効率を向上、安定性を保証
- CountingSort/RadixSort: 整数型でUIntマッピング可能な場合の線形時間ソート
- AbstractRange最適化: searchsorted系関数でO(1)計算
- sortperm_int_range: 整数配列で値域が小さい場合の特殊最適化

## セキュリティ考慮事項

- ScratchQuickSortのピボット選択はhash関数ベースであり、ランダム性は保証されない。ただし、実用上は問題とならない
- sort!はin-place操作のため、入力配列を直接変更する。並行アクセス時は注意が必要

## 備考

- QuickSort/MergeSortは後方互換性のために残されているが、内部的にはInitialOptimizationsを通じて適応型パイプラインにディスパッチされる
- PartialQuickSortもBracketedSort+ScratchQuickSortの組み合わせに変換される
- NTupleのソートはJulia 1.12以降でサポート（9要素以下はアンロールmergesort、10要素以上はVector経由）
- sortpermはデフォルトでDEFAULT_UNSTABLE（Perm orderingで安定性を保証）

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造とアルゴリズム型を理解する

Algorithm抽象型とその具体的なサブタイプ群。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | sort.jl | `base/sort.jl` | Algorithm抽象型（46行目）とexport一覧（17-44行目） |
| 1-2 | sort.jl | `base/sort.jl` | InsertionSortAlg（807行目）、SMALL_ALGORITHM（835行目） |
| 1-3 | sort.jl | `base/sort.jl` | ScratchQuickSort構造体（1076-1084行目）：lo, hi, nextフィールド |
| 1-4 | sort.jl | `base/sort.jl` | DefaultStable/DefaultUnstable（1550行目, 1570行目）とDEFAULT_STABLE/DEFAULT_UNSTABLE定数（1563行目, 1580行目） |
| 1-5 | sort.jl | `base/sort.jl` | _DEFAULT_ALGORITHMS_FOR_VECTORS（1582-1592行目）：アルゴリズムパイプライン全体構成 |

**読解のコツ**: Julia Sortモジュールのアルゴリズムは入れ子のstruct構造で表現される。各structはnextフィールドで次のアルゴリズムを保持し、_sort!のディスパッチチェーンを形成する。_DEFAULT_ALGORITHMS_FOR_VECTORSの入れ子構造を読むと、パイプライン全体の流れを把握できる。

#### Step 2: InitialOptimizationsパイプラインを理解する

ソート前の最適化パス群。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | sort.jl | `base/sort.jl` | InitialOptimizations構築関数（1475-1480行目）：SubArray→Missing→Bool→Small{10}→IEEEFloat |
| 2-2 | sort.jl | `base/sort.jl` | SubArrayOptimization（557-576行目）：SubArrayのunwrap |
| 2-3 | sort.jl | `base/sort.jl` | MissingOptimization（587-688行目）：Missing値の末尾移動 |
| 2-4 | sort.jl | `base/sort.jl` | BoolOptimization（744-770行目）：Bool配列のカウントベースソート |
| 2-5 | sort.jl | `base/sort.jl` | IEEEFloatOptimization（701-742行目）：NaN処理+UInt変換 |

#### Step 3: 主要ソートアルゴリズムを理解する

InsertionSort、ScratchQuickSort、CountingSort、RadixSort。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | sort.jl | `base/sort.jl` | InsertionSort._sort!（837-854行目）：シンプルな挿入ソート |
| 3-2 | sort.jl | `base/sort.jl` | partition!関数（1090-1121行目）：ハッシュベースピボット選択とパーティション |
| 3-3 | sort.jl | `base/sort.jl` | ScratchQuickSort._sort!（1123-1170行目付近）：スクラッチスペース使用のクイックソート |
| 3-4 | sort.jl | `base/sort.jl` | CountingSort._sort!（950-978行目）：カウントベースのソート |
| 3-5 | sort.jl | `base/sort.jl` | RadixSort._sort!（1018-1050行目付近）：基数ソート |

#### Step 4: 公開API（sort!/sort/sortperm/searchsorted）を理解する

ユーザー向けインタフェース。

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | sort.jl | `base/sort.jl` | sort!関数（1734-1743行目）：メインエントリーポイント |
| 4-2 | sort.jl | `base/sort.jl` | sort関数（1782行目）：copymutable+sort! |
| 4-3 | sort.jl | `base/sort.jl` | sortperm関数（1968-1996行目）：Perm orderingを使用 |
| 4-4 | sort.jl | `base/sort.jl` | searchsortedfirst/searchsortedlast（186-240行目）：二分探索実装 |
| 4-5 | sort.jl | `base/sort.jl` | issorted関数（50-97行目）：ソート済み判定 |
| 4-6 | sort.jl | `base/sort.jl` | sort!多次元配列版（2189-2220行目）：dims指定ソート |

### プログラム呼び出し階層図

```
sort!(v; alg, lt, by, rev, order, scratch)      [1734行目]
    |
    +-- defalg(v)                                 [1622-1626行目: DEFAULT_STABLE/UNSTABLE選択]
    +-- ord(lt, by, rev, order)                   [Ordering構築]
    +-- maybe_apply_initial_optimizations(alg)    [2398-2401行目]
    +-- _sort!(v, alg, order, kw)                 [適応型パイプライン]
            |
            +-- InitialOptimizations [1475-1480行目]
            |       +-- SubArrayOptimization     [557行目: SubArrayのunwrap]
            |       +-- MissingOptimization       [587行目: Missing値末尾移動]
            |       +-- BoolOptimization          [744行目: Bool配列O(n)ソート]
            |       +-- Small{10}                 [791行目: 10要素以下→InsertionSort]
            |       +-- IEEEFloatOptimization     [701行目: NaN/符号処理]
            |
            +-- IsUIntMappable分岐 [772行目]
            |       |
            |       +-- [UIntMappable] Small{40} → CheckSorted → ComputeExtrema
            |       |       → ConsiderCountingSort → ConsiderRadixSort
            |       |       → Small{80} → ScratchQuickSort
            |       |
            |       +-- [非UIntMappable] StableCheckSorted → ScratchQuickSort
            |
            +-- InsertionSort._sort!              [837行目: O(n^2)挿入ソート]
            +-- ScratchQuickSort._sort!           [1123行目: partition!使用]
            |       +-- partition!                [1090行目: ピボット選択+分割]
            |       +-- make_scratch              [505行目: スクラッチスペース管理]
            +-- CountingSort._sort!               [950行目: カウントソート]
            +-- RadixSort._sort!                  [1018行目: 基数ソート]

sortperm(v; ...)                                  [1968行目]
    +-- sort!(ix; order=Perm(order, vec(A)))       [Perm orderingでインデックスソート]

searchsortedfirst(v, x, lo, hi, o)               [186行目]
    +-- 二分探索（O(log n)）
    +-- AbstractRange特殊化（O(1)）               [258行目]
```

### データフロー図

```
[入力]                          [処理]                                    [出力]

v, order              ────────> InitialOptimizations                ────> 最適化済みv, order
                                  (SubArray/Missing/Bool/Float処理)

最適化済みv, order    ────────> IsUIntMappable分岐                 ────> アルゴリズム選択
                                  → CountingSort/RadixSort/ScratchQuickSort

v                     ────────> sort!(v; ...)                       ────> v（ソート済み）
v                     ────────> sort(v; ...)                        ────> new_v（ソート済みコピー）
v                     ────────> sortperm(v; ...)                    ────> ix（置換ベクトル）
sorted_v, x          ────────> searchsorted(v, x)                  ────> range（等値範囲）
v                     ────────> issorted(v)                         ────> Bool
A, dims               ────────> sort!(A; dims)                      ────> A（次元ソート済み）
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| sort.jl | `base/sort.jl` | ソース | Sortモジュール全体（アルゴリズム、API、二分探索等） |
| ordering.jl | `base/ordering.jl` | ソース | Ordering型定義（Forward, Reverse, By, Lt, Perm等） |
| abstractarray.jl | `base/abstractarray.jl` | ソース | copymutable等のユーティリティ |
| subarray.jl | `base/subarray.jl` | ソース | SubArrayOptimizationの対象型 |
