ソートアルゴリズムをGoで実装してみた
はじめに バックエンドエンジニアのロードマップに沿ってエンジニアとしての自己肯定感を養うシリーズです。
マージソート マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を 1 個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。
出典：wikipedia「マージソート」より引用
最悪の計算量が O(n log n) であるから少なくとも O(n^2)よりは速いんだろうなという印象（雑すぎるか）
以下「ソートを極める！ 〜 なぜソートを学ぶのか 〜」を元に実装してみた（なるべくソースを見ないで実装を試みたがマージする箇所は折れた、、）
package main import ( "fmt" "time" "github.com/uh-zz/traning/algorithm/shuffle" ) func main() { // ランダムな要素 n 個のスライス取得 input := shuffle.RandomIntList(n) inputLength := len(input) // マージソート MergeSort(&input, 0, inputLength) } // MergeSort マージソート func MergeSort(input \*[]int, left, right int) { // 要素数1つの場合は抜ける if right-left == 1 { return } // 配列を２つに分けるインデックス middle := left + (right-left)/2 // 配列左側 MergeSort(input, left, middle) // 配列右側 MergeSort(input, middle, right) var buffer []int // 左側と右側をバッファにためる（右側反転） for index := left; index < middle; index++ { buffer = append(buffer, (*input)[index]) } for index := right - 1; index >= middle; index-- { buffer = append(buffer, (*input)[index]) } // マージする scopeLeft := 0 scopeRight := len(buffer) - 1 for index := left; index < right; index++ { if buffer[scopeLeft] <= buffer[scopeRight] { // 左側採用 (*input)[index] = buffer[scopeLeft] scopeLeft++ } else { // 右側採用 (*input)[index] = buffer[scopeRight] scopeRight-- } } } これ考えたのぶっ飛んでるなあと思って Wikipedia 見てたら、考案者がフォン・ノイマンでやっぱりぶっ飛んでた（凄すぎ）
