👻

Dart 標準の sort() を理解する -なぜ34件から挙動が変わるのか

に公開

TL;DR

  • Dart の List.sort() は仕様上 「安定性が保証されていない」
  • 実装詳細としては、33件以下は安定(InsertionSort)だが、34件以上で不安定(Dual-Pivot Quicksort) に切り替わる
  • 順序を維持したい場合は、package:collection の mergeSort を使うべき

きっかけ

ある Flutter パッケージを使用していて、「データが少ないときは問題ないのに、34件を超えるとリストの順序がおかしくなる」という奇妙な現象に遭遇しました。
調査したところ、該当パッケージの Issue にも報告がありました(調査時点では Openで根本原因の言及もなし)。

grouped_list issue #167

原因は、そのパッケージが内部で List.sort() を使用しており、Dart 標準の sort() が 安定ソートではない(Unstable Sort) ためでした。

もしかすると同じように内部で sort() を使っているパッケージが他にもあるかもしれないので、この挙動を理解しておくと役立つかもしれません。

例えば、「カテゴリ順に並べるが、同じカテゴリ内は登録順(元の順序)を維持したい」というケースで問題になります。

// カテゴリでソートするが、同カテゴリ内は登録順を維持したい
items.sort((a, b) => a.category.compareTo(b.category));

// 期待: [食品A, 食品B], [日用品A, 日用品B]... (登録順)
// 実際: [食品B, 食品A], [日用品A, 日用品B]... (シャッフルされる!)

なぜ 34件以上でこの現象が起きるのか、公式ドキュメントと SDK の実装を確認してみます。


公式ドキュメントの内容

まず、実装を見る前に公式の仕様を確認しましょう。
List.sort() の公式ドキュメント には以下のように明記されています。

The sort is not guaranteed to be stable.
(ソートの安定性は保証されません)

つまり、仕様として「安定ソートではない」 ことが宣言されています。
たとえ現在の実装で偶然うまく動いていたとしても、この仕様がある限り、順序維持を List.sort() に期待するコードを書くべきではありません。


安定ソートと不安定ソート

用語を整理しておきます。

安定ソート(Stable Sort)

比較結果が等しい(同じキーを持つ)要素の相対的な順序が、ソート後も維持される アルゴリズムです。
元のリストで「A → B」の順なら、ソート後も必ず「A → B」になります。

  • 代表例: マージソート、挿入ソート

不安定ソート(Unstable Sort)

同じキーを持つ要素の順序が保証されない アルゴリズムです。
元のリストで「A → B」の順でも、ソート後に「B → A」に入れ替わる可能性があります。

  • 代表例: クイックソート、ヒープソート

Dart SDK の実装を追う

では、なぜ「34件」という謎の境界線が存在するのでしょうか?
Dart SDK のソースコード(sdk/lib/internal/sort.dart)を確認してみました。

https://github.com/dart-lang/sdk/blob/main/sdk/lib/internal/sort.dart

しきい値の定義

※実装詳細であり、変更される可能性があります

// sdk/lib/internal/sort.dart
static const int _INSERTION_SORT_THRESHOLD = 32;

アルゴリズムの分岐

// sdk/lib/internal/sort.dart
static void _doSort<E>(List<E> a, int left, int right, int Function(E, E) compare) {
  if ((right - left) <= _INSERTION_SORT_THRESHOLD) {
    _insertionSort(a, left, right, compare);  // 安定ソート (Insertion Sort)
  } else {
    _dualPivotQuicksort(a, left, right, compare);  // 不安定ソート (Dual-Pivot Quicksort)
  }
}

なぜ 34件なのか?

条件式は (right - left) <= 32 です。
リストのインデックスにおいて right = length - 1、left = 0 なので、要素数 (length) との関係は以下のようになります。

要素数 (length) right - left <= 32? 使用されるアルゴリズム
33 32 ✅ TRUE InsertionSort(安定)
34 33 ❌ FALSE Dual-Pivot Quicksort(不安定)

つまり、33件までは安定ソート(挿入ソート)が使われるため順序が維持されていたが、34件になった瞬間に不安定ソート(クイックソート)に切り替わり、順序が崩れる というのが今回の原因の正体です。

なぜ小さい配列で InsertionSort を使うのか?

Dart SDK のコードには以下のコメントがあります:

This class implements the dual-pivot quicksort algorithm as presented in Vladimir Yaroslavskiy's paper.

原論文(Vladimir Yaroslavskiy)では、小さい配列に対して InsertionSort を使う最適化が含まれています。

  • InsertionSort: O(n²) だがオーバーヘッドが小さく、小さい配列では高速
  • Quicksort: O(n log n) だが再帰やピボット選択のコストがある

小さい配列では InsertionSort のほうが速いため、しきい値以下では切り替えています。原論文では 27 がしきい値でしたが、Dart SDK では 32 に調整されています。


検証コードと実行結果

DartPad 等で以下のコードを実行すると、実際の挙動を確認できます。
すべての要素が「同じキー」を持つリストを作り、ソート前後でインデックスがどう変わるかを見ます。

import 'package:collection/collection.dart';

void main() {
  print('=== 要素数 33(Insertion Sort が使われる)===');
  test(33);

  print('\n=== 要素数 34(Dual-Pivot Quicksort が使われる)===');
  test(34);
}

class Item {
  final int key;            // 比較に使うキー
  final int originalIndex;  // 元の並び順確認用

  Item(this.key, this.originalIndex);

  @override
  String toString() => '($key,$originalIndex)';
}

void test(int count) {
  // すべて同じ key を持つ要素を生成
  final items1 = List.generate(count, (i) => Item(0, i));
  final items2 = List<Item>.from(items1);

  // =========================
  // List.sort() の確認
  // =========================
  print('\n--- List.sort() ---');
  print('ソート前:');
  print(items1.map((e) => e.originalIndex).toList());

  // key のみで比較(全要素が等しい)
  items1.sort((a, b) => a.key.compareTo(b.key));

  print('ソート後:');
  print(items1.map((e) => e.originalIndex).toList());

  // =========================
  // mergeSort() の確認
  // =========================
  print('\n--- mergeSort()(常に安定)---');
  print('ソート前:');
  print(items2.map((e) => e.originalIndex).toList());

  mergeSort(items2, compare: (a, b) => a.key.compareTo(b.key));

  print('ソート後:');
  print(items2.map((e) => e.originalIndex).toList());
}

実行結果

=== 要素数 33(Insertion Sort が使われる)===

--- List.sort() ---
ソート前:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
ソート後:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

--- mergeSort()(常に安定)---
ソート前:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]
ソート後:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]

=== 要素数 34(Dual-Pivot Quicksort が使われる)===

--- List.sort() ---
ソート前:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]
ソート後:
[11, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 12, 13, 14, 15, 16, 17, 18, 19, 20, 33, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 21]

--- mergeSort()(常に安定)---
ソート前:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]
ソート後:
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33]

解決策(順序を維持したい場合)

順序を維持したい(安定ソートを行いたい)場合の解決策です。

package:collection の mergeSort を使う

Dart 公式チームが提供している package:collection に含まれる mergeSort は安定ソートです。

import 'package:collection/collection.dart';

// items.sort(...) の代わりにこれを使う
mergeSort(items, compare: (a, b) => a.priority.compareTo(b.priority));

まとめ

  • Dart の List.sort() は 安定性が保証されていない。
  • 実装上、34件以上 のリストをソートすると順序が崩れる(Dual-Pivot Quicksort)。
  • 順序を維持したい場合は、迷わず package:collection の mergeSort を使おう。

今回初めて記事を書いたので間違っているところなどあればご遠慮なくご指摘ください!

参考

Discussion