この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "安定ソート" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2022年5月）

安定ソート（あんていソート、stable sort）とは、ソート（並べ替え）のアルゴリズムのうち、順位が同等な複数のデータのソート前の前後関係が、ソート後も保存されるものをいう。つまり、ソート途中の各状態において、常に順位の位置関係を保っていることをいう。

たとえば、学生番号順に整列済みの学生データを、テストの点数順で安定ソートを用いて並べ替えたとき、ソート後のデータにおいて、同じ点数の学生は学生番号順で並ぶようになっている。

例１：学生番号順　成績データ学生番号生徒名テスト成績
010A子419
011B男366
012C美402
013D生453
014E上419
015F崎402

例２：成績順　安定ソート学生番号生徒名テスト成績
011B男366
012C美402
015F崎402
010A子419
014E上419
013D生453

例３：成績順　不安定ソート学生番号生徒名テスト成績
011B男366
015F崎402
012C美402
014E上419
010A子419
013D生453


生徒番号015が012の先に来ており、また014も010より先に来ている。

元の生徒番号順が保持されていないため不安定ソートとなる。

安定でないソート法を用いる場合でも、整列したいデータに元のデータ列の順序を追加しておき、ソートする際にその情報を参照するようにすれば、安定ソートに変更できる。形式的には、ソートしたい項目と元の順番を表す項目のペアを辞書式順序でソートする、ということである。この方法は（入力データ自体が元々順番を表す項目を含んでいるのでない限り）元の順番を表す情報を記憶する必要がある。すなわち、長さ n の入力に対し、0 から n-1 までの連番を一時的に記憶するのだから、 O ( n log ⁡ n ) {\displaystyle O(n\log n)} の記憶容量を必要とする（必要となる一時変数の個数という意味では O ( n ) {\displaystyle O(n)} ）。したがって内部ソートが必要な場合には使えない。
関連項目

基数ソート（ラディックスソート）

逆写像ソート

シェーカーソート

挿入ソート

バケットソート

バブルソート

マージソート