golang: Insert to a sorted slice

Question

What's the most efficient way of inserting an element to a sorted slice?

I tried a couple of things but all ended up using at least 2 appends which as I understand makes a new copy of the slice

Answer 1

Here is how to insert into a sorted slice of strings:

Go Playground Link to full example: https://play.golang.org/p/4RkVgEpKsWq

func Insert(ss []string, s string) []string {
    i := sort.SearchStrings(ss, s)
    ss = append(ss, "")
    copy(ss[i+1:], ss[i:])
    ss[i] = s
    return ss
}

Answer 2

You could use a heap:

package main

import (
   "container/heap"
   "sort"
)

type slice struct { sort.IntSlice }
func (s slice) Pop() interface{} { return 0 }

func (s *slice) Push(x interface{}) {
   (*s).IntSlice = append((*s).IntSlice, x.(int))
}

func main() {
   s := &slice{
      sort.IntSlice{11, 10, 14, 13},
   }
   heap.Init(s)
   heap.Push(s, 12)
   println(s.IntSlice[0] == 10)
}

Note that a heap is not strictly sorted, but the "minimum element" is guaranteed to be the first element. Also I did not implement the Pop function in my example, you would want to do that.

https://golang.org/pkg/container/heap