Go スライスのソート順を維持したまま要素を追加する

スライスのソートを維持したまま要素を追加する関数 appendSorted の実装

func appendSorted[S ~[]E, E cmp.Ordered](s S, e E) S {
        i, _ := slices.BinarySearch(s, e)
        return slices.Insert(s, i, e)
}

挙動

s = []int{}
s = appendSorted(s, 4)  // [4]
s = appendSorted(s, 1)  // [1 4]
s = appendSorted(s, 9)  // [1 4 9]
s = appendSorted(s, 5)  // [1 4 5 9]
s = appendSorted(s, 3)  // [1 3 4 5 9]
s = appendSorted(s, 11) // [1 3 4 5 9 11]

計算量

配列の長さを とすると、BinarySearch は , Insert は だから、 appendSorted は 。一方、単純に append と sort する実装だと、 だから、早くなっている。平衡二分木を使えば、もっと早くなりそうだけど、コードも短いし十分実用的でしょう。