golang: Insert to a sorted slice

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

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
}

If the slice has enough capacity then there's no need for a new copy.
The elements after the insert position can be shifted to the right.
Only when the slice doesn't have enough capacity,
a new slice and copying all values will be necessary.

Keep in mind that slices are not designed for fast insertion.
So there won't be a miracle solution here using slices.
You could create a custom data structure to make this more efficient,
but obviously there will be other trade-offs.

One point that can be optimized in the process is finding the insertion point quickly. If the slice is sorted, then you can use binary search to perform this in O(log n) time.
However, this might not matter much,
considering the expensive operation of copying the end of the slice,
or reallocating when necessary.

I like @likebike's answer but it only works for strings. Here is the generic version that will work for a slice of any ordered type (requires Go 1.18):

func Insert[T constraints.Ordered](ts []T, t T) []T {
	var dummy T
	ts = append(ts, dummy) // extend the slice

	i, _ := slices.BinarySearch(ts, t) // find slot
	copy(ts[i+1:], ts[i:])             // make room
	ts[i] = t
	return ts
}

Note that this uses the package golang.org/x/exp/slices but this will almost certainly be included in the std Go library in Go 1.19.

Try it in the Go Playground

There are two parts to the problem: finding where to insert the value and inserting the value.

Use the sort package search functions to efficiently find the insertion index using binary search.

Use a single call to append to efficiently insert a value into a slice:

// insertAt inserts v into s at index i and returns the new slice.
func insertAt(data []int, i int, v int) []int {
	if i == len(data) {
		// Insert at end is the easy case.
		return append(data, v)
	}

	// Make space for the inserted element by shifting
	// values at the insertion index up one index. The call
	// to append does not allocate memory when cap(data) is
	// greater ​than len(data).
	data = append(data[:i+1], data[i:]...)

	// Insert the new element.
	data[i] = v

	// Return the updated slice.
	return data
}

Here's the code for inserting a value a sorted slice:

func insertSorted(data []int, v int) []int {
	i := sort.Search(len(data), func(i int) bool { return data[i] >= v })
	return insertAt(data, i, v)
}

The code in this answer uses a slice of int. Adjust the type to match your actual data.

The call to sort.Search in this answer can be replaced with a call to the helper function sort.SearchInts. I show sort.Search in this answer because the function applies to a slice of any type.

If you do not want to add duplicate values, check the value at the search index before inserting:

func insertSortedNoDups(data []int, v int) []int {
	i := sort.Search(len(data), func(i int) bool { return data[i] >= v })
	if i < len(data) && data[i] == v {
		return data
	}
	return insertAt(data, i, v)
}

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

There are two approaches mentioned here to insert into the slice when the position i is known:

data = append(data, "")
copy(data[i+1:], data[i:])
data[i] = s

and

data = append(data[:i+1], data[i:]...)
data[i] = s

I just benchmarked both with go1.18beta2, and the first solution is approximately 10% faster.

no dependency, generic data type with duplicated options. (go 1.18)

time complexity : Log2(n) + 1

import "golang.org/x/exp/constraints"
import "golang.org/x/exp/slices"

func InsertionSort[T constraints.Ordered](array []T, value T, canDupicate bool) []T {
	pos, isFound := slices.BinarySearch(array, value)
    if canDupicate || !isFound {
       array = slices.Insert(array, pos, value)
    }
	return array
}

full version : https://go.dev/play/p/P2_ou2Fqs37

play : https://play.golang.org/p/dUGmPurouxA

array1 := []int{1, 3, 4, 5}

	//want to insert at index 1
	insertAtIndex := 1
	temp := append([]int{}, array1[insertAtIndex:]...)
	array1 = append(array1[0:insertAtIndex], 2)
	array1 = append(array1, temp...)

	fmt.Println(array1)

You can try the below code. It basically uses the golang sort package

package main

import "sort"
import "fmt"

func main() {

	data := []int{20, 21, 22, 24, 25, 26, 28, 29, 30, 31, 32}
	var items = []int{23, 27}
	for _, x := range items {
		i := sort.Search(len(data), func(i int) bool { return data[i] >= x })
		if i < len(data) && data[i] == x {
			fmt.Println(i)
		} else {
			data = append(data, 0)
			copy(data[i+1:], data[i:])
			data[i] = x
		}
		fmt.Println(data)
	}
}