go-sort - 背景
歴史的経緯
ソートアルゴリズムの発展
1945年、John von Neumann がマージソートを発明しました。これは分割統治法を使用した最初のソートアルゴリズムでした。
その後、様々なソートアルゴリズムが開発されました：
- 1959年: シェルソート
- 1960年: クイックソート（Tony Hoare）
- 1964年: ヒープソート
スタックソートの研究
2つのスタックでのソートは、計算理論の研究対象です。最小操作数を求める問題はNP困難であることが知られています。
コンピュータサイエンス的な意味
計算量
| アルゴリズム | 最良 | 平均 | 最悪 | 空間 |
|---|---|---|---|---|
| バブルソート | O(n) | O(n²) | O(n²) | O(1) |
| クイックソート | O(n log n) | O(n log n) | O(n²) | O(log n) |
| マージソート | O(n log n) | O(n log n) | O(n log n) | O(n) |
| ヒープソート | O(n log n) | O(n log n) | O(n log n) | O(1) |
スタックマシン
スタックは多くの場面で使用されます：
- 関数呼び出し（コールスタック）
- 逆ポーランド記法の計算
- 構文解析
実践での活用
go-sort で学ぶアルゴリズム思考は、以下の場面で役立ちます：
- データベースのインデックス構築
- 検索結果のランキング
- メモリ効率の最適化